On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing

DOI10.1007/978-3-030-43662-9_7OpenAlexW2397531432MaRDI QIDQ5098771

Oded Goldreich

Publication date: 30 August 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.433.3120

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Related Items

Sublinear-time algorithms for counting star subgraphs via edge sampling

Cites Work

• Unnamed Item
• Property testing lower bounds via communication complexity
• Property testing. Current research and surveys
• The space complexity of approximating the frequency moments
• Property testing and its connection to learning and approximation
• On the efficiency of local decoding procedures for error-correcting codes
• Locally testable codes and PCPs of almost-linear length
• On Testing Computability by Small Width OBDDs
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• The Probabilistic Communication Complexity of Set Intersection
• Testing of Clustering
• Testing the diameter of graphs
• Communication Complexity
• Robust Characterizations of Polynomials with Applications to Program Testing
• Short Locally Testable Codes and Proofs: A Survey in Two Parts
• lgorithmic and Analysis Techniques in Property Testing
• Introduction to Property Testing
• Some 3CNF Properties Are Hard to Test
• Testing problems with sublearning sample complexity
• Property testing in bounded degree graphs

This page was built for publication: On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing