Non-interactive proofs of proximity (Q1745962): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q113906244
@@ Property / Wikidata QID: Q113906244 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2473767456
@@ Property / OpenAlex ID: W2473767456 / rank @@
+Normal rank
@@ Property / cites work @@
+Algebrization
@@ Property / cites work: Algebrization / rank @@
+Normal rank
@@ Property / cites work @@
+A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
+Normal rank
@@ Property / cites work @@
+Regular Languages are Testable with a Constant Number of Queries
+Normal rank
@@ Property / cites work @@
+Improved low-degree testing and its applications
@@ Property / cites work: Improved low-degree testing and its applications / rank @@
+Normal rank
@@ Property / cites work @@
+Streaming graph computations with a helpful advisor
+Normal rank
@@ Property / cites work @@
+Q3615896
@@ Property / cites work: Q3615896 / rank @@
+Normal rank
@@ Property / cites work @@
+Sampling algorithms
@@ Property / cites work: Sampling algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
+Normal rank
@@ Property / cites work @@
+Testing Juntas: A Brief Survey
@@ Property / cites work: Testing Juntas: A Brief Survey / rank @@
+Normal rank
@@ Property / cites work @@
+Property testing lower bounds via communication complexity
+Normal rank
@@ Property / cites work @@
+BPP and the polynomial hierarchy
@@ Property / cites work: BPP and the polynomial hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity measures and decision tree complexity: a survey.
+Normal rank
@@ Property / cites work @@
+Lower bounds for sampling algorithms for estimating the average
+Normal rank
@@ Property / cites work @@
+Annotations for Sparse Data Streams
@@ Property / cites work: Annotations for Sparse Data Streams / rank @@
+Normal rank
@@ Property / cites work @@
+Annotations in Data Streams
@@ Property / cites work: Annotations in Data Streams / rank @@
+Normal rank
@@ Property / cites work @@
+Q4601830
@@ Property / cites work: Q4601830 / rank @@
+Normal rank
@@ Property / cites work @@
+An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
+Normal rank
@@ Property / cites work @@
+Practical verified computation with streaming interactive proofs
+Normal rank
@@ Property / cites work @@
+Finding cycles and trees in sublinear time
@@ Property / cites work: Finding cycles and trees in sublinear time / rank @@
+Normal rank
@@ Property / cites work @@
+Streaming Verification in Data Analysis
@@ Property / cites work: Streaming Verification in Data Analysis / rank @@
+Normal rank
@@ Property / cites work @@
+Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
+Normal rank
@@ Property / cites work @@
+Fast approximate probabilistically checkable proofs
+Normal rank
@@ Property / cites work @@
+Partial tests, universal tests and decomposability
+Normal rank
@@ Property / cites work @@
+On the query complexity of testing orientations for being Eulerian
+Normal rank
@@ Property / cites work @@
+Q3002823
@@ Property / cites work: Q3002823 / rank @@
+Normal rank
@@ Property / cites work @@
+Highly resilient correctors for polynomials
@@ Property / cites work: Highly resilient correctors for polynomials / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic vs non-deterministic graph property testing
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Property testing. Current research and surveys
@@ Property / cites work: Property testing. Current research and surveys / rank @@
+Normal rank
@@ Property / cites work @@
+Short Locally Testable Codes and Proofs: A Survey in Two Parts
+Normal rank
@@ Property / cites work @@
+Introduction to Testing Graph Properties
@@ Property / cites work: Introduction to Testing Graph Properties / rank @@
+Normal rank
@@ Property / cites work @@
+On Multiple Input Problems in Property Testing.
@@ Property / cites work: On Multiple Input Problems in Property Testing. / rank @@
+Normal rank
@@ Property / cites work @@
+Property testing and its connection to learning and approximation
+Normal rank
@@ Property / cites work @@
+Q4578332
@@ Property / cites work: Q4578332 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4601820
@@ Property / cites work: Q4601820 / rank @@
+Normal rank
@@ Property / cites work @@
+Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
+Normal rank
@@ Property / cites work @@
+On the complexity of interactive proofs with bounded communication
+Normal rank
@@ Property / cites work @@
+Sparse pseudorandom distributions
@@ Property / cites work: Sparse pseudorandom distributions / rank @@
+Normal rank
@@ Property / cites work @@
+A sublinear bipartiteness tester for bounded degree graphs
+Normal rank
@@ Property / cites work @@
+Property testing in bounded degree graphs
@@ Property / cites work: Property testing in bounded degree graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On Proximity-Oblivious Testing
@@ Property / cites work: On Proximity-Oblivious Testing / rank @@
+Normal rank
@@ Property / cites work @@
+On Sample-Based Testers
@@ Property / cites work: On Sample-Based Testers / rank @@
+Normal rank
@@ Property / cites work @@
+On proximity oblivious testing
@@ Property / cites work: On proximity oblivious testing / rank @@
+Normal rank
@@ Property / cites work @@
+On the randomness complexity of property testing
@@ Property / cites work: On the randomness complexity of property testing / rank @@
+Normal rank
@@ Property / cites work @@
+Two-Sided Error Proximity Oblivious Testing
@@ Property / cites work: Two-Sided Error Proximity Oblivious Testing / rank @@
+Normal rank
@@ Property / cites work @@
+Locally testable codes and PCPs of almost-linear length
+Normal rank
@@ Property / cites work @@
+On interactive proofs with a laconic prover
@@ Property / cites work: On interactive proofs with a laconic prover / rank @@
+Normal rank
@@ Property / cites work @@
+The Knowledge Complexity of Interactive Proof Systems
+Normal rank
@@ Property / cites work @@
+Arthur-Merlin Streaming Complexity
@@ Property / cites work: Arthur-Merlin Streaming Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Non-Interactive Proofs of Proximity
@@ Property / cites work: Non-Interactive Proofs of Proximity / rank @@
+Normal rank
@@ Property / cites work @@
+Arguments of Proximity
@@ Property / cites work: Arguments of Proximity / rank @@
+Normal rank
@@ Property / cites work @@
+The Probabilistic Communication Complexity of Set Intersection
+Normal rank
@@ Property / cites work @@
+On the efficiency of local decoding procedures for error-correcting codes
+Normal rank
@@ Property / cites work @@
+Q3549724
@@ Property / cites work: Q3549724 / rank @@
+Normal rank
@@ Property / cites work @@
+Communication Complexity
@@ Property / cites work: Communication Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+One way functions and pseudorandom generators
@@ Property / cites work: One way functions and pseudorandom generators / rank @@
+Normal rank
@@ Property / cites work @@
+Non-Deterministic Graph Property Testing
@@ Property / cites work: Non-Deterministic Graph Property Testing / rank @@
+Normal rank
@@ Property / cites work @@
+Algebraic methods for interactive proof systems
@@ Property / cites work: Algebraic methods for interactive proof systems / rank @@
+Normal rank
@@ Property / cites work @@
+Private vs. common random bits in communication complexity
+Normal rank
@@ Property / cites work @@
+Property Testing of Massively Parametrized Problems – A Survey
+Normal rank
@@ Property / cites work @@
+On limited nondeterminism and the complexity of the V-C dimension
+Normal rank
@@ Property / cites work @@
+lgorithmic and Analysis Techniques in Property Testing
+Normal rank
@@ Property / cites work @@
+Interactive proofs of proximity
@@ Property / cites work: Interactive proofs of proximity / rank @@
+Normal rank
@@ Property / cites work @@
+Robust Characterizations of Polynomials with Applications to Program Testing
+Normal rank
@@ Property / cites work @@
+The multiparty communication complexity of set disjointness
+Normal rank
@@ Property / cites work @@
+Efficient checking of polynomials and proofs and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+Semi-Streaming Algorithms for Annotated Graph Streams
+Normal rank