Non-interactive proofs of proximity
From MaRDI portal
Publication:1745962
DOI10.1007/S00037-016-0136-9zbMATH Open1391.68098OpenAlexW2473767456WikidataQ113906244 ScholiaQ113906244MaRDI QIDQ1745962FDOQ1745962
Authors: Tom Gur, Ron D. Rothblum 
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
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
- Property testing and its connection to learning and approximation
- Locally testable codes and PCPs of almost-linear length
- Sampling algorithms: lower bounds and applications
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Property testing in bounded degree graphs
- Introduction to testing graph properties
- Property testing. A learning theory perspective
- The Probabilistic Communication Complexity of Set Intersection
- Communication Complexity
- Robust Characterizations of Polynomials with Applications to Program Testing
- Algorithmic and analysis techniques in property testing
- Computational Complexity
- One way functions and pseudorandom generators
- BPP and the polynomial hierarchy
- On interactive proofs with a laconic prover
- On limited nondeterminism and the complexity of the V-C dimension
- On the complexity of interactive proofs with bounded communication
- The Knowledge Complexity of Interactive Proof Systems
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- The multiparty communication complexity of set disjointness
- A sublinear bipartiteness tester for bounded degree graphs
- Complexity measures and decision tree complexity: a survey.
- Private vs. common random bits in communication complexity
- Algebrization: a new barrier in complexity theory
- Non-interactive proofs of proximity
- A separation of NP and conp in multiparty communication complexity
- Annotations in Data Streams
- Title not available (Why is that?)
- Annotations for Sparse Data Streams
- On the query complexity of testing orientations for being Eulerian
- Algebraic property testing: the role of invariance
- Algebraic methods for interactive proof systems
- Property testing of massively parametrized problems -- a survey
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Regular languages are testable with a constant number of queries
- Practical verified computation with streaming interactive proofs
- Highly resilient correctors for polynomials
- Lower bounds for sampling algorithms for estimating the average
- On the efficiency of local decoding procedures for error-correcting codes
- Property testing lower bounds via communication complexity
- Improved low-degree testing and its applications
- Deterministic vs non-deterministic graph property testing
- Non-deterministic graph property testing
- Property testing. Current research and surveys
- Testing juntas: a brief survey
- On the randomness complexity of property testing
- On Sample-Based Testers
- Universal locally testable codes
- Arguments of proximity (extended abstract)
- Sparse pseudorandom distributions
- Fast approximate probabilistically checkable proofs
- Strong locally testable codes with relaxed local decoders
- Finding cycles and trees in sublinear time
- Partial tests, universal tests and decomposability
- On Proximity-Oblivious Testing
- Two-sided error proximity oblivious testing (extended abstract)
- Interactive proofs of proximity: delegating computation in sublinear time
- On multiple input problems in property testing
- Proofs of proximity for context-free languages and read-once branching programs
- Streaming Verification in Data Analysis
- Semi-streaming algorithms for annotated graph streams
- Short locally testable codes and proofs: a survey in two parts
- On proximity oblivious testing
- Arthur-Merlin streaming complexity
Cited In (16)
- Every Set in P Is Strongly Testable Under a Suitable Encoding
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- Zero-knowledge proofs of proximity
- Proofs of proximity for context-free languages and read-once branching programs
- On the power of relaxed local decoding algorithms
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- 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
- Arguments of proximity (extended abstract)
- Smooth and strong PCPs
- Sound 3-query PCPPs are long
- Relaxed locally correctable codes
- Proofs of proximity for distribution testing
- An exponential separation between MA and AM proofs of proximity
- Succinct interactive oracle proofs: applications and limitations
- Non-interactive proofs of proximity
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)
