On the Effect of the Proximity Parameter on Property Testers

DOI10.1007/978-3-030-43662-9_5MaRDI QIDQ5098769zbMATH OpenOpenAlexFDO

Authors Oded Goldreich

Publication date 30 August 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.422.870

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• On Proximity-Oblivious Testing
• On proximity oblivious testing
• Two-sided error proximity oblivious testing
• Two-sided error proximity oblivious testing (extended abstract)
• Hierarchy theorems for testing properties in size-oblivious query complexity

Cites work

• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Introduction to Property Testing
• 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

This page was built for publication: On the Effect of the Proximity Parameter on Property Testers

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