An Exponential Separation Between MA and AM Proofs of Proximity
From MaRDI portal
Publication:5002752
DOI10.4230/LIPIcs.ICALP.2018.73zbMath1499.68117OpenAlexW2887969491MaRDI QIDQ5002752
No author found.
Publication date: 28 July 2021
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9077/pdf/LIPIcs-ICALP-2018-73.pdf/
Related Items (2)
Unnamed Item ⋮ Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the randomness complexity of property testing
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Private vs. common random bits in communication complexity
- Non-interactive proofs of proximity
- Fast approximate probabilistically checkable proofs
- Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation
- Streaming graph computations with a helpful advisor
- Arthur-Merlin streaming complexity
- The Multiparty Communication Complexity of Set Disjointness
- Algebrization
- Partial tests, universal tests and decomposability
- Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication
- Property testing and its connection to learning and approximation
- Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions
- Algebraic methods for interactive proof systems
- Semi-Streaming Algorithms for Annotated Graph Streams
- A Hierarchy Theorem for Interactive Proofs of Proximity
- Robust Characterizations of Polynomials with Applications to Program Testing
- Annotations in Data Streams
- lgorithmic and Analysis Techniques in Property Testing
- Introduction to Property Testing
- Interactive proofs of proximity
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
This page was built for publication: An Exponential Separation Between MA and AM Proofs of Proximity
