A hierarchy theorem for interactive proofs of proximity
From MaRDI portal
Recommendations
Cites work
- Algebraic methods for interactive proof systems
- Algebrization: a new barrier in complexity theory
- Annotations for Sparse Data Streams
- Annotations in Data Streams
- Are there interactive protocols for co-NP languages?
- Arguments of proximity (extended abstract)
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Arthur-Merlin streaming complexity
- Computational Complexity
- Constant-round interactive proofs for delegating computation
- Delegation for bounded space
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Efficient multiparty protocols via log-depth threshold formulae. (Extended abstract)
- Fast approximate probabilistically checkable proofs
- Highly resilient correctors for polynomials
- How to delegate computations
- scientific article; zbMATH DE number 5485522 (Why is no real title available?)
- scientific article; zbMATH DE number 1335880 (Why is no real title available?)
- scientific article; zbMATH DE number 6829278 (Why is no real title available?)
- Improved low-degree testing and its applications
- Improving and extending the testing of distributions for shape-restricted properties
- Interactive PCP
- Interactive proofs of proximity: delegating computation in sublinear time
- Introduction to Property Testing
- IP = PSPACE
- IP = PSPACE using error-correcting codes
- Locally testable codes and PCPs of almost-linear length
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Monotone Circuits for the Majority Function
- Non-deterministic exponential time has two-prover interactive protocols
- Non-interactive proofs of proximity
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On (Valiant’s) Polynomial-Size Monotone Formula for Majority
- On interactive proofs with a laconic prover
- On learning and testing dynamic environments
- On sample-based testers
- On the power of interaction
- On transformation of interactive proofs that preserve the prover's complexity
- Partial tests, universal tests and decomposability
- Practical verified computation with streaming interactive proofs
- Proofs of proximity for context-free languages and read-once branching programs
- Property testing and its connection to learning and approximation
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Robust Characterizations of Polynomials with Applications to Program Testing
- Semi-streaming algorithms for annotated graph streams
- Short monotone formulae for the majority function
- Streaming Verification in Data Analysis
- Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation
- Strong locally testable codes with relaxed local decoders
- The Knowledge Complexity of Interactive Proof Systems
- The multiparty communication complexity of set disjointness
- The random oracle hypothesis is false
- Universal locally testable codes
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- Zero-information protocols and unambiguity in Arthur-Merlin communication (extended abtract)
Cited in
(18)- An adaptivity hierarchy theorem for property testing
- 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
- Optimal Proximity Proofs Revisited
- Arguments of proximity (extended abstract)
- Interactive proofs and the hardness of approximating cliques
- An exponential separation between MA and AM proofs of proximity
- scientific article; zbMATH DE number 7250162 (Why is no real title available?)
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- Constant-round arguments from one-way functions
- Holographic SNARGs for P and batch-NP from (polynomially hard) learning with errors
- Constant-round arguments for batch-verification and bounded-space computations from one-way functions
- Asymptotically-good RLCCs with \((\log n)^{2+o(1)}\) queries
- Streaming zero-knowledge proofs
- Public-coin three-round zero-knowledge from learning with errors and keyless multi-collision-resistant hash
- Blaze: fast SNARKs from interleaved RAA codes
- Doubly-efficient batch verification in statistical zero-knowledge
- Rate-1 zero-knowledge proofs from one-way functions
This page was built for publication: A hierarchy theorem for interactive proofs of proximity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638092)
