Testing graph blow-up

DOI10.1007/978-3-642-22935-0_33MaRDI QIDQ5894224zbMATH OpenOpenAlexFDO

Authors Lidor Avigad, Oded Goldreich

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

property testinggraph blow-upgraph propertiesadaptivity vs. non-adaptivityone-sided vs. two-sided error

Mathematics Subject Classification ID

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

Recommendations

• Testing graph blow-up
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Algorithmic aspects of property testing in the dense graphs model
• A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers

Cites work

• scientific article; zbMATH DE number 6469238 (Why is no real title available?)
• A combinatorial characterization of the testable graph properties, it's all about regularity
• Efficient testing of large graphs
• Hierarchy theorems for property testing
• Lower bounds for sampling algorithms for estimating the average
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing graph blow-up
• Three theorems regarding testing graph properties

Cited in

(3)

• Efficient testing without efficient regularity
• Graph limits and parameter testing
• Testing graph blow-up

This page was built for publication: Testing graph blow-up

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