Sub-constant error probabilistically checkable proof of almost-linear size

DOI10.1007/S00037-009-0278-0MaRDI QIDQ626681zbMATHOpenAlexFDO

Authors Dana Moshkovitz, Ran Raz

Publication date 18 February 2011

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-009-0278-0

zbMATH Keywords

probabilistically checkable proof (PCP)almost-linear sizebalanced curvessub-constant error

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Constant rate PCPs for circuit-SAT with sublinear query complexity
• Publication:2762515
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Small PCPs with low query complexity
• Two-query PCP with subconstant error

Cited in

(7)

• Tight bounds on subexponential time approximation of set cover and related problems
• Composition of low-error 2-query PCPs using decodable PCPs
• Constant-space, constant-randomness verifiers with arbitrarily small error
• ETH-hardness of approximating 2-CSPs and directed Steiner network
• Mathematics of computation through the lens of linear equations and lattices
• Three-player entangled XOR games are NP-hard to approximate
• Nearly-linear size holographic proofs

This page was built for publication: Sub-constant error probabilistically checkable proof of almost-linear size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q626681)