Contemplations on Testing Graph Properties

DOI10.1007/978-3-642-22670-0_35zbMath1291.05195OpenAlexW141284932MaRDI QIDQ3088201

Oded Goldreich

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2006/555/

zbMATH Keywords

graph propertiesProperty testing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

On the Query Complexity of Estimating the Distance to Hereditary Graph Properties, The Complexity of Public-Key Cryptography

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A sublinear bipartiteness tester for bounded degree graphs
• Testing k-colorability
• A combinatorial characterization of the testable graph properties
• Introduction to Testing Graph Properties
• Property testing and its connection to learning and approximation
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Every monotone graph property is testable
• Testing versus estimation of graph properties
• On the Benefits of Adaptivity in Property Testing of Dense Graphs
• The complexity of promise problems with applications to public-key cryptography
• Three theorems regarding testing graph properties
• Testing the diameter of graphs
• Testing properties of directed graphs: acyclicity and connectivity*
• Tight Bounds for Testing Bipartiteness in General Graphs
• Testing subgraphs in large graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• lgorithmic and Analysis Techniques in Property Testing
• Efficient testing of large graphs
• Property testing in bounded degree graphs