A Hierarchy Theorem for Interactive Proofs of Proximity
From MaRDI portal
Publication:4638092
DOI10.4230/LIPIcs.ITCS.2017.39zbMath1402.68096OpenAlexW2771519522MaRDI QIDQ4638092
Publication date: 3 May 2018
Full work available at URL: https://dblp.uni-trier.de/db/conf/innovations/innovations2017.html#GurR17
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Randomized algorithms (68W20)
Related Items
An adaptivity hierarchy theorem for property testing ⋮ A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ An Exponential Separation Between MA and AM Proofs of Proximity ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- On the power of interaction
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Are there interactive protocols for co-NP languages?
- Highly resilient correctors for polynomials
- The random oracle hypothesis is false
- On interactive proofs with a laconic prover
- Fast approximate probabilistically checkable proofs
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Streaming graph computations with a helpful advisor
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- Arthur-Merlin streaming complexity
- Improved low-degree testing and its applications
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
- Practical verified computation with streaming interactive proofs
- IP = PSPACE Using Error-Correcting Codes
- Efficient Multiparty Protocols via Log-Depth Threshold Formulae
- 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
- On transformation of interactive proofs that preserve the prover's complexity
- Short monotone formulae for the majority function
- Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
- Arguments of Proximity
- Streaming Verification in Data Analysis
- Interactive PCP
- Locally testable codes and PCPs of almost-linear length
- Monotone Circuits for the Majority Function
- Annotations in Data Streams
- The Knowledge Complexity of Interactive Proof Systems
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Semi-Streaming Algorithms for Annotated Graph Streams
- Improving and extending the testing of distributions for shape-restricted properties
- On Learning and Testing Dynamic Environments
- Robust Characterizations of Polynomials with Applications to Program Testing
- On Sample-Based Testers
- On (Valiant’s) Polynomial-Size Monotone Formula for Majority
- How to delegate computations
- Constant-round interactive proofs for delegating computation
- Introduction to Property Testing
- Annotations for Sparse Data Streams
- The multiparty communication complexity of set disjointness
- Delegation for bounded space
- Interactive proofs of proximity
- Computational Complexity
