Two-sided error proximity oblivious testing (extended abstract)

DOI10.1007/978-3-642-32512-0_48MaRDI QIDQ3167426zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Igor Shinkar

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32512-0_48

Mathematics Subject Classification ID

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

Recommendations

• Two-sided error proximity oblivious testing
• 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

Cited in

(9)

• Tolerant versus intolerant testing for Boolean properties
• Non-interactive proofs of proximity
• Proximity Oblivious Testing and the Role of Invariances
• Proofs of proximity for context-free languages and read-once branching programs
• Two-sided error proximity oblivious testing
• GSF-locality is not sufficient for proximity-oblivious testing
• On being far from far and on dual problems in property testing (extended abstract)
• On Proximity-Oblivious Testing
• On proximity oblivious testing

This page was built for publication: Two-sided error proximity oblivious testing (extended abstract)

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