Non-interactive proofs of proximity
From MaRDI portal
Publication:1745962
DOI10.1007/s00037-016-0136-9zbMath1391.68098OpenAlexW2473767456WikidataQ113906244 ScholiaQ113906244MaRDI QIDQ1745962
Publication date: 18 April 2018
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/113748/1/WRAP-non-interactive-proofs-proximity-Gur-2018.pdf
Related Items
Unnamed Item, A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification, Succinct interactive oracle proofs: applications and limitations, An Exponential Separation Between MA and AM Proofs of Proximity, An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity, Smooth and strong PCPs, Every Set in P Is Strongly Testable Under a Suitable Encoding, On the Power of Relaxed Local Decoding Algorithms, Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of interactive proofs with bounded communication
- Deterministic vs non-deterministic graph property testing
- On the randomness complexity of property testing
- Lower bounds for sampling algorithms for estimating the average
- Property testing lower bounds via communication complexity
- Property testing. Current research and surveys
- BPP and the polynomial hierarchy
- One way functions and pseudorandom generators
- Private vs. common random bits in communication complexity
- Highly resilient correctors for polynomials
- On interactive proofs with a laconic prover
- On limited nondeterminism and the complexity of the V-C dimension
- Complexity measures and decision tree complexity: a survey.
- Fast approximate probabilistically checkable proofs
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Streaming graph computations with a helpful advisor
- A sublinear bipartiteness tester for bounded degree graphs
- Improved low-degree testing and its applications
- Regular Languages are Testable with a Constant Number of Queries
- Practical verified computation with streaming interactive proofs
- Finding cycles and trees in sublinear time
- Algebrization
- On Multiple Input Problems in Property Testing.
- Partial tests, universal tests and decomposability
- Non-Interactive Proofs of Proximity
- On Sample-Based Testers
- On Proximity-Oblivious Testing
- Introduction to Testing Graph Properties
- Property testing and its connection to learning and approximation
- Two-Sided Error Proximity Oblivious Testing
- On the query complexity of testing orientations for being Eulerian
- On the efficiency of local decoding procedures for error-correcting codes
- Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
- Arguments of Proximity
- Streaming Verification in Data Analysis
- Locally testable codes and PCPs of almost-linear length
- Annotations in Data Streams
- The Knowledge Complexity of Interactive Proof Systems
- Sparse pseudorandom distributions
- The Probabilistic Communication Complexity of Set Intersection
- Algebraic methods for interactive proof systems
- Semi-Streaming Algorithms for Annotated Graph Streams
- Communication Complexity
- Robust Characterizations of Polynomials with Applications to Program Testing
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
- Testing Juntas: A Brief Survey
- Short Locally Testable Codes and Proofs: A Survey in Two Parts
- Property Testing of Massively Parametrized Problems – A Survey
- On proximity oblivious testing
- Sampling algorithms
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- lgorithmic and Analysis Techniques in Property Testing
- Arthur-Merlin Streaming Complexity
- Annotations for Sparse Data Streams
- Non-Deterministic Graph Property Testing
- The multiparty communication complexity of set disjointness
- Interactive proofs of proximity
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Computational Complexity
- Property testing in bounded degree graphs
