On proximity oblivious testing

DOI10.1145/1536414.1536436MaRDI QIDQ5172707zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Dana Ron

Publication date 4 February 2015

Published in Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1536414.1536436

zbMATH Keywords

graph propetiesproperty testing

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Recommendations

• On Proximity-Oblivious Testing
• Two-sided error proximity oblivious testing
• Two-sided error proximity oblivious testing (extended abstract)
• Proximity Oblivious Testing and the Role of Invariances
• Proximity oblivious testing and the role of invariances

Cited in

(16)

• Non-interactive proofs of proximity
• Tolerant property testing and distance approximation
• Two-sided error proximity oblivious testing
• Recognizing coverage functions
• Partial tests, universal tests and decomposability
• On Proximity-Oblivious Testing
• Two-sided error proximity oblivious testing (extended abstract)
• Invariance in property testing
• Testing Linear-Invariant Non-linear Properties: A Short Report
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• On sample-based testers
• On the Effect of the Proximity Parameter on Property Testers
• Proximity Oblivious Testing and the Role of Invariances
• Testing graph blow-up
• Proximity oblivious testing and the role of invariances
• GSF-locality is not sufficient for proximity-oblivious testing

This page was built for publication: On proximity oblivious testing

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