A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers

DOI10.1007/978-3-642-25591-5_54zbMath1350.68285OpenAlexW2963604144MaRDI QIDQ3104651

Jeremy Hurwitz

Publication date: 16 December 2011

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25591-5_54

zbMATH Keywords

property testingsublinear-time algorithmshierarchy theoremadaptive vs non-adaptive queriesdense-graph model

Mathematics Subject Classification ID

Randomized algorithms (68W20)

This page was built for publication: A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers