scientific article; zbMATH DE number 7650076

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.9MaRDI QIDQ5875460

Subhash A. Khot, Devanathan Thiruvenkatachari, Prahladh Harsha, Euiwoong Lee

Publication date: 3 February 2023

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

compositionprobabilistically checkable proofsPCP3LINlow soundness error

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• A Sample of Samplers: A Computational Perspective on Sampling
• Proof verification and the hardness of approximation problems
• Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies
• Two-query PCP with subconstant error
• Probabilistic checking of proofs
• A Parallel Repetition Theorem
• Inapproximability Results for Computational Problems on Lattices
• Analytical approach to parallel repetition
• Composition of Low-Error 2-Query PCPs Using Decodable PCPs
• Some optimal inapproximability results
• On the advantage over a random assignment

This page was built for publication: