2026-08-12T06:26:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10113 2024-03-06T10:45:24Z ddc:004 open_access

Adaptive Boolean Monotonicity Testing in Total Influence Time Chakrabarty, Deeparnab Seshadhri, C. Property Testing Monotonicity Testing Influence of Boolean Functions Testing monotonicity of a Boolean function f:{0,1}^n -> {0,1} is an important problem in the field of property testing. It has led to connections with many interesting combinatorial questions on the directed hypercube: routing, random walks, and new isoperimetric theorems. Denoting the proximity parameter by epsilon, the best tester is the non-adaptive O~(epsilon^{-2}sqrt{n}) tester of Khot-Minzer-Safra (FOCS 2015). A series of recent results by Belovs-Blais (STOC 2016) and Chen-Waingarten-Xie (STOC 2017) have led to Omega~(n^{1/3}) lower bounds for adaptive testers. Reducing this gap is a significant question, that touches on the role of adaptivity in monotonicity testing of Boolean functions. We approach this question from the perspective of parametrized property testing, a concept recently introduced by Pallavoor-Raskhodnikova-Varma (ACM TOCT 2017), where one seeks to understand performance of testers with respect to parameters other than just the size. Our result is an adaptive monotonicity tester with one-sided error whose query complexity is O(epsilon^{-2}I(f)log^5 n), where I(f) is the total influence of the function. Therefore, adaptivity provably helps monotonicity testing for low influence functions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Deeparnab Chakrabarty and C. Seshadhri 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.20 urn:nbn:de:0030-drops-101133 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.20 eng https://creativecommons.org/licenses/by/3.0/legalcode