A separation theorem in property testing

DOI10.1007/S00493-008-2321-1zbMATH Open1174.05063OpenAlexW2082435079MaRDI QIDQ949795FDOQ949795

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

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

zbMATH Keywords

property testingerror parameter

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

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

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)