A $\tilde{O}(n)$ Non-Adaptive Tester for Unateness

Abstract

Khot and Shinkar (RANDOM, 2016) recently describe an adaptive, $O(n\log (n)/\epsilon )$-query tester for unateness of Boolean functions $f:\{0,1{\}}^n\to \{0,1\}$. In this note we describe a simple non-adaptive, $O(n\log (n/\epsilon )/\epsilon )$ -query tester for unateness for functions over the hypercube with any ordered range.

We mention the relation of our algorithm to Levin's investment strategy, as pointed out by Oded Goldreich

References in corpus (1)

• New algorithms and lower bounds for monotonicity testing

Cited by in corpus (1)

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