On the Benefits of Adaptivity in Property Testing of Dense Graphs

DOI10.1007/978-3-540-74208-1_38MaRDI QIDQ3603491zbMATH OpenOpenAlexFDO

Authors Mira Gonen, Dana Ron

Publication date 17 February 2009

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-540-74208-1_38

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Pattern recognition, speech recognition (68T10)

Recommendations

• On the benefits of adaptivity in property testing of dense graphs
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Algorithmic aspects of property testing in the dense graphs model
• A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers

Cited in

(10)

• An adaptivity hierarchy theorem for property testing
• Introduction to testing graph properties
• Contemplations on Testing Graph Properties
• Testing juntas: a brief survey
• Introduction to testing graph properties
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• An adaptivity hierarchy theorem for property testing
• Algorithmic aspects of property testing in the dense graphs model
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• On the benefits of adaptivity in property testing of dense graphs

This page was built for publication: On the Benefits of Adaptivity in Property Testing of Dense Graphs

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