A separation theorem in property testing

DOI10.1007/S00493-008-2321-1MaRDI QIDQ949795zbMATH OpenOpenAlexFDO

Authors Noga Alon, Asaf Shapira

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

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

Recommendations

• Brief announcement: Erasure-resilience versus tolerance to errors
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Property testing and its connection to learning and approximation
• scientific article; zbMATH DE number 1241385
• Two-sided error proximity oblivious testing

Cites work

• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 1559556 (Why is no real title available?)
• scientific article; zbMATH DE number 1857651 (Why is no real title available?)
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A combinatorial characterization of the testable graph properties, it's all about regularity
• Efficient testing of large graphs
• Every monotone graph property is testable
• Graph Theory and Probability
• On a problem of K. Zarankiewicz
• On extremal problems of graphs and generalized graphs
• Property testing and its connection to learning and approximation
• Ramanujan graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Testing the diameter of graphs
• Three theorems regarding testing graph properties
• Tight Bounds for Testing Bipartiteness in General Graphs

Cited in

(8)

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

This page was built for publication: A separation theorem in property testing

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