Short PCPs with Polylog Query Complexity
From MaRDI portal
Publication:3624377
DOI10.1137/050646445zbMath1172.68025OpenAlexW2087900794MaRDI QIDQ3624377
Publication date: 30 April 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/050646445
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Other types of codes (94B60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (41)
Succinct non-interactive arguments via linear interactive proofs ⋮ Quantum Locally Testable Codes ⋮ Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries ⋮ Parallel Hashing via List Recoverability ⋮ Interactive Oracle Proofs ⋮ ZK-PCPs from leakage-resilient secret sharing ⋮ Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs ⋮ Asymptotically quasi-optimal cryptography ⋮ A PCP theorem for interactive proofs and applications ⋮ Linear-size constant-query IOPs for delegating computation ⋮ HyperPlonk: Plonk with linear-time prover and high-degree custom gates ⋮ Parallelizable delegation from LWE ⋮ Unnamed Item ⋮ A toolbox for barriers on interactive oracle proofs ⋮ Scalable and transparent proofs over all large fields, via elliptic curves. ECFFT. II ⋮ The hunting of the SNARK ⋮ 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 ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Combinatorial PCPs with efficient verifiers ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Shorter arithmetization of nondeterministic computations ⋮ Composition of semi-LTCs by two-wise tensor products ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Composition of Low-Error 2-Query PCPs Using Decodable PCPs ⋮ Smooth and strong PCPs ⋮ Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs ⋮ SPARKs: succinct parallelizable arguments of knowledge ⋮ Marlin: preprocessing zkSNARKs with universal and updatable SRS ⋮ Short Locally Testable Codes and Proofs ⋮ Every Set in P Is Strongly Testable Under a Suitable Encoding ⋮ Imperfect gaps in Gap-ETH and PCPs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity ⋮ Spartan: efficient and general-purpose zkSNARKs without trusted setup ⋮ Computational Integrity with a Public Random String from Quasi-Linear PCPs ⋮ Combinatorial PCPs with short proofs
This page was built for publication: Short PCPs with Polylog Query Complexity
