An adaptivity hierarchy theorem for property testing

DOI10.4230/LIPICS.CCC.2017.27MaRDI QIDQ5111157zbMATH OpenFDO

Authors Clement L. Canonne, Tom Gur

Publication date 26 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2017.27

zbMATH Keywords

coding theoryhierarchy theoremsproperty testing

Mathematics Subject Classification ID

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

Recommendations

• An adaptivity hierarchy theorem for property testing
• A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers
• On the benefits of adaptivity in property testing of dense graphs
• On the Benefits of Adaptivity in Property Testing of Dense Graphs
• Algorithmic Aspects of Property Testing in the Dense Graphs Model

Cited in

(9)

• An adaptivity hierarchy theorem for property testing
• Hierarchy theorems for testing properties in size-oblivious query complexity
• A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers
• Hierarchy Theorems for Property Testing
• Hierarchy theorems for property testing
• Erasure-Resilient Property Testing
• Hierarchy theorems for property testing
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Optimal unateness testers for real-valued functions: Adaptivity helps

This page was built for publication: An adaptivity hierarchy theorem for property testing

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