Interactive proofs of proximity

DOI10.1145/2488608.2488709zbMath1293.68250OpenAlexW2135952940MaRDI QIDQ5495850

Avi Wigderson, Guy N. Rothblum, Salil P. Vadhan

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

interactive proofssublinear algorithms

Mathematics Subject Classification ID

Related Items (20)

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Proofs of proximity for context-free languages and read-once branching programs ⋮ Delegating RAM Computations ⋮ More efficient amortization of exact zero-knowledge proofs for LWE ⋮ A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes ⋮ Zero-Knowledge Proofs of Proximity ⋮ Proofs of Proximity for Distribution Testing ⋮ An Exponential Separation Between MA and AM Proofs of Proximity ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Non-interactive proofs of proximity ⋮ Unnamed Item ⋮ Rational Sumchecks ⋮ Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP ⋮ \textsc{Fractal}: post-quantum and transparent recursive proofs from holography ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ Interactive proofs for social graphs

This page was built for publication: Interactive proofs of proximity