On the Effect of the Proximity Parameter on Property Testers

DOI10.1007/978-3-030-43662-9_5OpenAlexW2407524400MaRDI QIDQ5098769FDOQ5098769

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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)