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
Publication: 9th January 2018 16:22
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