Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
From MaRDI portal
Publication:5757456
DOI10.1137/S0097539705446962zbMath1127.68031OpenAlexW1970278864MaRDI QIDQ5757456
Publication date: 7 September 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539705446962
Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs, Cube vs. Cube Low Degree Test., Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries, Arguments of Proximity, Proofs of proximity for context-free languages and read-once branching programs, ZK-PCPs from leakage-resilient secret sharing, A PCP theorem for interactive proofs and applications, On the (In)security of Kilian-based SNARGs, Low-degree test with polynomially small error, Unnamed Item, Bridging a Small Gap in the Gap Amplification of Assignment Testers, Erasures versus errors in local decoding and property testing, Unnamed Item, Unnamed Item, Unnamed Item, Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes, Unnamed Item, The tensor product of two good codes is not necessarily robustly testable, On the rectangle method in proofs of robustness of tensor products, Erasure-Resilient Property Testing, Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms, PCPs and the hardness of generating synthetic data, Derandomized parallel repetition via structured PCPs, Relaxed Locally Correctable Codes, Combinatorial PCPs with efficient verifiers, An Exponential Separation Between MA and AM Proofs of Proximity, Shorter arithmetization of nondeterministic computations, Composition of semi-LTCs by two-wise tensor products, An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity, Non-interactive proofs of proximity, A PCP Characterization of AM, Revisiting alphabet reduction in Dinur’s PCP., Combinatorial algorithms for distributed graph coloring, Towards lower bounds on locally testable codes via density arguments, Limitation on the Rate of Families of Locally Testable Codes, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Invariance in Property Testing, Composition of Low-Error 2-Query PCPs Using Decodable PCPs, Unnamed Item, Unnamed Item, Unnamed Item, Smooth and strong PCPs, Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs, Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP, Efficient Probabilistically Checkable Debates, \textsc{Fractal}: post-quantum and transparent recursive proofs from holography, Short Locally Testable Codes and Proofs, Bravely, Moderately: A Common Theme in Four Recent Works, A combinatorial characterization of smooth LTCs and applications, From Local to Robust Testing via Agreement Testing, Combinatorial Algorithms for Distributed Graph Coloring, Unnamed Item, Constant-Round Interactive Proofs for Delegating Computation, A combination of testability and decodability by tensor products, On Dinur’s proof of the PCP theorem, Computational Integrity with a Public Random String from Quasi-Linear PCPs, Direct Sum Testing, Combinatorial PCPs with short proofs
