Recommendations
- Non-interactive proofs of proximity
- Interactive proofs of proximity: delegating computation in sublinear time
- Zero-knowledge proofs of proximity
- Proofs of proximity for context-free languages and read-once branching programs
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
Cites work
- scientific article; zbMATH DE number 6829278 (Why is no real title available?)
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- A separation of NP and conp in multiparty communication complexity
- A sublinear bipartiteness tester for bounded degree graphs
- Algebraic methods for interactive proof systems
- Algebraic property testing: the role of invariance
- Algebrization: a new barrier in complexity theory
- Algorithmic and analysis techniques in property testing
- Annotations for Sparse Data Streams
- Annotations in Data Streams
- Arguments of proximity (extended abstract)
- Arthur-Merlin streaming complexity
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- BPP and the polynomial hierarchy
- Communication Complexity
- Complexity measures and decision tree complexity: a survey.
- Computational Complexity
- Deterministic vs non-deterministic graph property testing
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Fast approximate probabilistically checkable proofs
- Finding cycles and trees in sublinear time
- Highly resilient correctors for polynomials
- Improved low-degree testing and its applications
- Interactive proofs of proximity: delegating computation in sublinear time
- Introduction to testing graph properties
- Locally testable codes and PCPs of almost-linear length
- Lower bounds for sampling algorithms for estimating the average
- Non-deterministic graph property testing
- Non-interactive proofs of proximity
- On Proximity-Oblivious Testing
- On Sample-Based Testers
- On interactive proofs with a laconic prover
- On limited nondeterminism and the complexity of the V-C dimension
- On multiple input problems in property testing
- On proximity oblivious testing
- On the complexity of interactive proofs with bounded communication
- On the efficiency of local decoding procedures for error-correcting codes
- On the query complexity of testing orientations for being Eulerian
- On the randomness complexity of property testing
- One way functions and pseudorandom generators
- Partial tests, universal tests and decomposability
- Practical verified computation with streaming interactive proofs
- Private vs. common random bits in communication complexity
- Proofs of proximity for context-free languages and read-once branching programs
- Property testing and its connection to learning and approximation
- Property testing in bounded degree graphs
- Property testing lower bounds via communication complexity
- Property testing of massively parametrized problems -- a survey
- Property testing. A learning theory perspective
- Property testing. Current research and surveys
- Regular languages are testable with a constant number of queries
- Robust Characterizations of Polynomials with Applications to Program Testing
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Sampling algorithms: lower bounds and applications
- Semi-streaming algorithms for annotated graph streams
- Short locally testable codes and proofs: a survey in two parts
- Sparse pseudorandom distributions
- Streaming Verification in Data Analysis
- Strong locally testable codes with relaxed local decoders
- Testing juntas: a brief survey
- The Knowledge Complexity of Interactive Proof Systems
- The Probabilistic Communication Complexity of Set Intersection
- The multiparty communication complexity of set disjointness
- Two-sided error proximity oblivious testing (extended abstract)
- Universal locally testable codes
Cited in
(16)- Arguments of proximity (extended abstract)
- Every Set in P Is Strongly Testable Under a Suitable Encoding
- Relaxed locally correctable codes
- Proofs of proximity for distribution testing
- Smooth and strong PCPs
- An exponential separation between MA and AM proofs of proximity
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- Non-interactive proofs of proximity
- On the power of relaxed local decoding algorithms
- Succinct interactive oracle proofs: applications and limitations
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- Zero-knowledge proofs of proximity
- Sound 3-query PCPPs are long
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
- Proofs of proximity for context-free languages and read-once branching programs
- Proofs of proximity for context-free languages and read-once branching programs
This page was built for publication: Non-interactive proofs of proximity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1745962)
