Testing Graph Blow-Up

DOI10.1007/978-3-642-22670-0_18zbMath1343.68286OpenAlexW4237567744MaRDI QIDQ5894229

Oded Goldreich, Lidor Avigad

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://doi.org/10.1007/978-3-642-22670-0_18

zbMATH Keywords

graph propertiesproperty testinggraph blow-upadaptivity vs non-adaptivityone-sided vs two-sided error

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Testing graphs against an unknown distribution, Hierarchy theorems for property testing, Algorithmic Aspects of Property Testing in the Dense Graphs Model, Testing Graph Blow-Up

Cites Work

• Unnamed Item
• Lower bounds for sampling algorithms for estimating the average
• A combinatorial characterization of the testable graph properties
• Property testing and its connection to learning and approximation
• Hierarchy Theorems for Property Testing
• Three theorems regarding testing graph properties
• Robust Characterizations of Polynomials with Applications to Program Testing
• On proximity oblivious testing
• Efficient testing of large graphs