ECCC-Report TR17-111https://eccc.weizmann.ac.il/report/2017/111Comments and Revisions published for TR17-111en-usThu, 22 Jun 2017 17:35:29 +0300
Paper TR17-111
| A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube |
Roksana Baleshzar,
Ramesh Krishnan S. Pallavoor,
Sofya Raskhodnikova,
C. Seshadhri,
Deeparnab Chakrabarty
https://eccc.weizmann.ac.il/report/2017/111A 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).Thu, 22 Jun 2017 17:35:29 +0300https://eccc.weizmann.ac.il/report/2017/111