Nearly-linear size holographic proofs

DOI10.1145/195058.195132zbMath1345.68180OpenAlexW2029859729MaRDI QIDQ2817611

Daniel A. Spielman, Alexander Polishchuk

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195132

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20)

Related Items

Algebraic testing and weight distributions of codes. ⋮ Fast approximate probabilistically checkable proofs ⋮ Local Reductions ⋮ Succinct non-interactive arguments via linear interactive proofs ⋮ Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries ⋮ Local reduction ⋮ Linear-size constant-query IOPs for delegating computation ⋮ Ligero: lightweight sublinear arguments without a trusted setup ⋮ Erasures versus errors in local decoding and property testing ⋮ Unnamed Item ⋮ Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ The tensor product of two good codes is not necessarily robustly testable ⋮ A novel elementary construction of matching vectors ⋮ On the rectangle method in proofs of robustness of tensor products ⋮ Derandomized parallel repetition via structured PCPs ⋮ Combinatorial PCPs with efficient verifiers ⋮ Lower bounds for adaptive locally decodable codes ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Shorter arithmetization of nondeterministic computations ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Unnamed Item ⋮ Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs ⋮ Limits on the Rate of Locally Testable Affine-Invariant Codes ⋮ Public Key Locally Decodable Codes with Short Keys ⋮ Short Locally Testable Codes and Proofs ⋮ Unnamed Item ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ Local correctability of expander codes ⋮ Combinatorial PCPs with short proofs