A separation theorem in property testing

DOI10.1007/s00493-008-2321-1zbMath1174.05063OpenAlexW2082435079MaRDI QIDQ949795

Asaf Shapira, Noga Alon

Publication date: 21 October 2008

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-008-2321-1

zbMATH Keywords

property testingerror parameter

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorics in computer science (68R05) Extremal combinatorics (05D99)

Related Items

Additive approximation for edge-deletion problems, Flexible Models for Testing Graph Properties, Local-vs-global combinatorics, Testable and untestable classes of first-order formulae, Introduction to Testing Graph Properties, Introduction to Testing Graph Properties, A unified framework for testing linear‐invariant properties, Relational Properties Expressible with One Universal Quantifier Are Testable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramanujan graphs
• Self-testing/correcting with applications to numerical problems
• On extremal problems of graphs and generalized graphs
• A combinatorial characterization of the testable graph properties
• Property testing and its connection to learning and approximation
• Graph Theory and Probability
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Every monotone graph property is testable
• 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
• On a problem of K. Zarankiewicz
• Efficient testing of large graphs