Two-sided error proximity oblivious testing

DOI10.1002/rsa.20582zbMath1352.68285OpenAlexW2166198137MaRDI QIDQ2795747

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 propertiesproperty testingone-sided vs two-sided error probabilityproximity-oblivious testerstesting properties of distributions

Mathematics Subject Classification ID

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

Related Items

Testing linear inequalities of subgraph statistics, Local-vs-global combinatorics, Erasure-Resilient Property Testing, Every Set in P Is Strongly Testable Under a Suitable Encoding

Cites Work

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