Non-Interactive Proofs of Proximity

DOI10.1145/2688073.2688079zbMath1364.68212OpenAlexW2097786318MaRDI QIDQ2989023

Tom Gur, Ron D. Rothblum

Publication date: 19 May 2017

Published in: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/113748/1/WRAP-non-interactive-proofs-proximity-Gur-2018.pdf

zbMATH Keywords

property testingprobabilistic proof systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Randomized algorithms (68W20)

Related Items (17)

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 ⋮ The landscape of communication complexity classes ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Relaxed Locally Correctable Codes ⋮ Zero-Knowledge Proofs of Proximity ⋮ Proofs of Proximity for Distribution Testing ⋮ 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 ⋮ Constant-Round Interactive Proofs for Delegating Computation

This page was built for publication: Non-Interactive Proofs of Proximity