Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity

DOI10.1145/2901294zbMath1410.68140OpenAlexW2556940513MaRDI QIDQ3177809

Or Meir, Yohay Kaplan, Eli Ben-Sasson, Swastik Kopparty, Henning Stichtenoth

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.353.2950

zbMATH Keywords

algebraic-geometric codesprobabilistically checkable proofserror-correcting codessublinear time algorithmsprobabilistic proof systemsPCPs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (10)

Interactive Oracle Proofs ⋮ Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier ⋮ Linear-size constant-query IOPs for delegating computation ⋮ Scalable and transparent proofs over all large fields, via elliptic curves. ECFFT. II ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Shorter arithmetization of nondeterministic computations ⋮ Sublinear Zero-Knowledge Arguments for RAM Programs ⋮ Combinatorial PCPs with short proofs

This page was built for publication: Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity