Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR17-111 | 2nd June 2017 08:42

#### A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube

TR17-111
Authors: Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri
Publication: 22nd June 2017 17:35
A Boolean function $f:\{0,1\}^d \to \{0,1\}$ is unate if, along each coordinate, the function is either nondecreasing or nonincreasing. In this note, we prove that any nonadaptive, one-sided error unateness tester must make $\Omega(\frac{d}{\log d})$ queries. This result improves upon the $\Omega(\frac{d}{\log^2 d})$ lower bound for the same class of testers due to Chen et al. (STOC, 2017).