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

Abstract

A Boolean function $f:\{0,1{\}}^d\mapsto \{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).

Cited by in corpus (2)

• Boolean Unateness Testing with $\tilde{O}(n^{3/4})$ Adaptive Queries
• Testing Unateness Nearly Optimally