Two-sided error proximity oblivious testing

DOI10.1002/RSA.20582MaRDI QIDQ2795747zbMATH OpenOpenAlexWikidataFDO

Authors Oded Goldreich, Igor Shinkar

Publication date 22 March 2016

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20582

zbMATH Keywords

graph propertiesone-sided vs two-sided error probabilityproperty testingproximity-oblivious testerstesting properties of distributions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Two-sided error proximity oblivious testing (extended abstract)
• On Proximity-Oblivious Testing
• On proximity oblivious testing
• Tolerant versus intolerant testing for Boolean properties
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error

Cites work

• Algorithmic aspects of property testing in the dense graphs model
• Effective Łojasiewicz inequalities in semialgebraic geometry
• Efficient testing of large graphs
• On Proximity-Oblivious Testing
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Three theorems regarding testing graph properties

Cited in

(14)

• On being far from far and on dual problems in property testing (extended abstract)
• Tolerant versus intolerant testing for Boolean properties
• On Proximity-Oblivious Testing
• Two-sided error proximity oblivious testing (extended abstract)
• Erasure-Resilient Property Testing
• Every Set in P Is Strongly Testable Under a Suitable Encoding
• On the Effect of the Proximity Parameter on Property Testers
• A Note on Tolerant Testing with One-Sided Error
• On proximity oblivious testing
• Proximity Oblivious Testing and the Role of Invariances
• Testing linear inequalities of subgraph statistics
• Local-vs-global combinatorics
• On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
• A separation theorem in property testing

This page was built for publication: Two-sided error proximity oblivious testing

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