Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR18-005 | 9th January 2018 08:32

Adaptive Boolean Monotonicity Testing in Total Influence Time

TR18-005
Authors: C. Seshadhri, Deeparnab Chakrabarty
Publication: 9th January 2018 16:22
Downloads: 173
Keywords:

Abstract:

The problem of testing monotonicity
of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ has received much attention
recently. Denoting the proximity parameter by $\varepsilon$, the best tester is the non-adaptive $\widetilde{O}(\sqrt{n}/\varepsilon^2)$ tester
of Khot-Minzer-Safra (FOCS 2015). Let $I(f)$ denote the total influence
of $f$. We give an adaptive tester whose running time is $I(f)poly(\varepsilon^{-1}\log n)$.

ISSN 1433-8092 | Imprint