Short PCPPs verifiable in polylogarithmic time with O(1) queries

DOI10.1007/S10472-009-9169-YzbMATH Open1184.68464OpenAlexW2007309095MaRDI QIDQ2379685FDOQ2379685

Authors: Thilo Mie 

Publication date: 19 March 2010

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-009-9169-y

Recommendations

• Short PCPs with projection queries
• scientific article; zbMATH DE number 1114044
• Sound 3-Query PCPPs Are Long
• Interactive PCP
• Query efficient PCPs with perfect completeness

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Computational Complexity
• Nearly-linear size holographic proofs
• Proof verification and the hardness of approximation problems
• Short PCPs with Polylog Query Complexity
• Probabilistic checking of proofs
• Interactive proofs and the hardness of approximating cliques
• Gadgets, Approximation, and Linear Programming
• Some optimal inapproximability results
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Universal Arguments and their Applications
• The PCP theorem by gap amplification

Cited In (18)

• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• Local reduction
• Smooth and strong PCPs
• Orion: zero knowledge proof with linear prover time
• ZK-PCPs from leakage-resilient secret sharing
• Towards hardness of approximation for polynomial time problems
• Simple PCPs with poly-log rate and query complexity
• Computational integrity with a public random string from quasi-linear PCPs
• Fast Reed-Solomon interactive oracle proofs of proximity
• Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier
• Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance
• Linear-size constant-query IOPs for delegating computation
• On uniformity and circuit lower bounds
• Rigid matrices from rectangular PCPs
• STIR: Reed-Solomon proximity testing with fewer queries
• Shorter arithmetization of nondeterministic computations
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
• Local reductions

This page was built for publication: Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries

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