Flexible Models for Testing Graph Properties

DOI10.1007/978-3-030-43662-9_19OpenAlexW2810136226MaRDI QIDQ5098784

Oded Goldreich

Publication date: 30 August 2022

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

Full work available at URL: https://doi.org/10.1007/978-3-030-43662-9_19

Mathematics Subject Classification ID

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

Cites Work

• A separation theorem in property testing
• A sublinear bipartiteness tester for bounded degree graphs
• Hierarchy theorems for testing properties in size-oblivious query complexity
• Property testing and its connection to learning and approximation
• Three theorems regarding testing graph properties
• Testing the diameter of graphs
• Tight Bounds for Testing Bipartiteness in General Graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing graphs in vertex-distribution-free models
• Introduction to Property Testing
• Efficient testing of large graphs
• Property testing in bounded degree graphs