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

DOI10.1007/S10472-009-9169-YMaRDI QIDQ2379685zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(23)

• Local reduction
• Smooth and strong PCPs
• ZK-PCPs from leakage-resilient secret sharing
• Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier
• Linear-size constant-query IOPs for delegating computation
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
• Local reductions
• Simple PCPs with poly-log rate and query complexity
• Towards hardness of approximation for polynomial time problems
• On uniformity and circuit lower bounds
• Shorter arithmetization of nondeterministic computations
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• Fast Reed-Solomon interactive oracle proofs of proximity
• Computational integrity with a public random string from quasi-linear PCPs
• Orion: zero knowledge proof with linear prover time
• Rigid matrices from rectangular PCPs
• Public-coin, complexity-preserving, succinct arguments of knowledge for NP from collision-resistance
• STIR: Reed-Solomon proximity testing with fewer queries
• The computational advantage of MIP* vanishes in the presence of noise
• Hamming weight proofs of proximity with one-sided error
• Proving as fast as computing: succinct arguments with constant prover overhead
• Local proofs approaching the witness length
• Linear prover IOPs in log star rounds

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)