Non-interactive proofs of proximity
type: Item
instance of: scholarly article
title: Non-interactive proofs of proximity
zbMATH Open document ID: 1391.68098
author: Tom Gur
author: Ron D. Rothblum
published in: Computational Complexity
publication date: 2018-04-18T00:00:00Z
full work available at URL: WRAP-non-interactive-proofs-proximity-Gur-2018.pdf
Mathematics Subject Classification ID: 68T15
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6861524
zbMATH Keywords: property testing
zbMATH Keywords: probabilistic proof systems
zbMATH Keywords: proofs of proximity
MaRDI profile type: Publication
Wikidata QID: Q113906244
OpenAlex ID: W2473767456
cites work: Algebrization
cites work: A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
cites work: Regular languages are testable with a constant number of queries
cites work: Improved low-degree testing and its applications
cites work: Streaming graph computations with a helpful advisor
cites work: Q3615896
cites work: Sampling algorithms
cites work: Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
cites work: Testing Juntas: A Brief Survey
cites work: Property testing lower bounds via communication complexity
cites work: BPP and the polynomial hierarchy
cites work: Complexity measures and decision tree complexity: a survey.
cites work: Lower bounds for sampling algorithms for estimating the average
cites work: Annotations for Sparse Data Streams
cites work: Annotations in Data Streams
cites work: Q4601830
cites work: An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
cites work: Practical verified computation with streaming interactive proofs
cites work: Finding cycles and trees in sublinear time
cites work: Streaming Verification in Data Analysis
cites work: Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
cites work: Fast approximate probabilistically checkable proofs
cites work: Partial tests, universal tests and decomposability
cites work: On the query complexity of testing orientations for being Eulerian
cites work: Q3002823
cites work: Highly resilient correctors for polynomials
cites work: Deterministic vs non-deterministic graph property testing
cites work: Computational Complexity
cites work: Property testing. Current research and surveys
cites work: Short Locally Testable Codes and Proofs: A Survey in Two Parts
cites work: Introduction to Testing Graph Properties
cites work: On Multiple Input Problems in Property Testing.
cites work: Property testing and its connection to learning and approximation
cites work: Q4578332
cites work: Q4601820
cites work: Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
cites work: On the complexity of interactive proofs with bounded communication
cites work: Sparse pseudorandom distributions
cites work: A sublinear bipartiteness tester for bounded degree graphs
cites work: Property testing in bounded degree graphs
cites work: On Proximity-Oblivious Testing
cites work: On Sample-Based Testers
cites work: On proximity oblivious testing
cites work: On the randomness complexity of property testing
cites work: Two-Sided Error Proximity Oblivious Testing
cites work: Locally testable codes and PCPs of almost-linear length
cites work: On interactive proofs with a laconic prover
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: Arthur-Merlin Streaming Complexity
cites work: Non-Interactive Proofs of Proximity
cites work: Arguments of Proximity
cites work: The Probabilistic Communication Complexity of Set Intersection
cites work: On the efficiency of local decoding procedures for error-correcting codes
cites work: Q3549724
cites work: Communication Complexity
cites work: One way functions and pseudorandom generators
cites work: Non-Deterministic Graph Property Testing
cites work: Algebraic methods for interactive proof systems
cites work: Private vs. common random bits in communication complexity
cites work: Property Testing of Massively Parametrized Problems – A Survey
cites work: On limited nondeterminism and the complexity of the V-C dimension

Non-interactive proofs of proximity (cites work)
cites work: lgorithmic and Analysis Techniques in Property Testing

Non-interactive proofs of proximity (cites work)
cites work: Interactive proofs of proximity

Non-interactive proofs of proximity (cites work)
cites work: Robust Characterizations of Polynomials with Applications to Program Testing

Non-interactive proofs of proximity (cites work)
cites work: The multiparty communication complexity of set disjointness

Non-interactive proofs of proximity (cites work)
cites work: Efficient checking of polynomials and proofs and the hardness of approximation problems

Non-interactive proofs of proximity (cites work)
cites work: Semi-Streaming Algorithms for Annotated Graph Streams

Non-interactive proofs of proximity (DOI)
DOI: 10.1007/S00037-016-0136-9