On Sample-Based Testers

DOI10.1145/2688073.2688080MaRDI QIDQ2989048zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Dana Ron

Publication date 19 May 2017

Published in Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

samplingproperty testingsublinear algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On sample-based testers
• On theorem prover-based testing
• A survey of combinatorial testing
• Towards a notion of testability
• A contribution to the theory of program testing
• scientific article; zbMATH DE number 4049566
• The test suite generation problem: optimal instances and their implications

Cited in

(7)

• Erasure-Resilient Property Testing
• On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition)
• Non-interactive proofs of proximity
• On sample-based testers
• A characterization of constant-sample testable properties
• The power and limitations of uniform samples in testing properties of figures
• The power and limitations of uniform samples in testing properties of figures

This page was built for publication: On Sample-Based Testers

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