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

DOI10.1007/978-3-030-43662-9_7MaRDI QIDQ5098771zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Property testing lower bounds via communication complexity
• Hierarchy theorems for testing properties in size-oblivious query complexity
• On the average-case complexity of property testing
• On the Randomness Complexity of Property Testing
• On the randomness complexity of property testing
• Property testing lower bounds via a generalization of randomized parity decision trees
• A comparison of two lower bound methods for communication complexity (extended abstract)
• Distribution testing lower bounds via reductions from communication complexity
• Distribution testing lower bounds via reductions from communication complexity
• Publication:4946045

Cites work

• Algorithmic and analysis techniques in property testing
• Communication Complexity
• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• Introduction to Property Testing
• Locally testable codes and PCPs of almost-linear length
• On testing computability by small width OBDDs
• On the efficiency of local decoding procedures for error-correcting codes
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Property testing lower bounds via communication complexity
• Property testing. Current research and surveys
• Robust Characterizations of Polynomials with Applications to Program Testing
• Short locally testable codes and proofs: a survey in two parts
• Some 3CNF Properties Are Hard to Test
• Testing of Clustering
• Testing problems with sublearning sample complexity
• Testing the diameter of graphs
• The Probabilistic Communication Complexity of Set Intersection
• The space complexity of approximating the frequency moments
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(1)

• Sublinear-time algorithms for counting star subgraphs via edge sampling

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5098771)