An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
From MaRDI portal
Publication:1983326
DOI10.1007/s00037-021-00212-3OpenAlexW3194732277WikidataQ113906242 ScholiaQ113906242MaRDI QIDQ1983326
Publication date: 10 September 2021
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-021-00212-3
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the randomness complexity of property testing
- Property testing lower bounds via communication complexity
- Quantum information and the PCP theorem
- 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
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- 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
- Non-Interactive Proofs of Proximity
- Property testing and its connection to learning and approximation
- Big Data on the Rise?
- Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
- Arguments of Proximity
- The Probabilistic Communication Complexity of Set Intersection
- 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
- Constant-round interactive proofs for delegating computation
- 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 \textsf{MA} and \textsf{AM} proofs of proximity
