2026-07-21T15:07:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7587 2024-03-06T10:40:41Z ddc:004 open_access

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces Chen, Xi Servedio, Rocco A. Tan, Li-Yang Waingarten, Erik property testing linear threshold functions monotonicity adaptivity We give a poly(log(n),1/epsilon)-query adaptive algorithm for testing whether an unknown Boolean function f:{-1, 1}^n -> {-1, 1}, which is promised to be a halfspace, is monotone versus epsilon-far from monotone. Since non-adaptive algorithms are known to require almost Omega(n^{1/2}) queries to test whether an unknown halfspace is monotone versus far from monotone, this shows that adaptivity enables an exponential improvement in the query complexity of monotonicity testing for halfspaces. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xi Chen and Rocco A. Servedio and Li-Yang Tan and Erik Waingarten 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.38 urn:nbn:de:0030-drops-75877 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.38 eng https://creativecommons.org/licenses/by/3.0/legalcode