Testing Graph Blow-Up

DOI10.1007/978-3-642-22935-0_33zbMath1343.68285OpenAlexW1507319950MaRDI QIDQ5894224

Oded Goldreich, Lidor Avigad

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_33

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

Efficient Testing without Efficient Regularity

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
• Three theorems regarding testing graph properties
• Robust Characterizations of Polynomials with Applications to Program Testing
• Hierarchy Theorems for Property Testing
• Testing Graph Blow-Up
• Efficient testing of large graphs