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

by Deeparnab Chakrabarty and C. Seshadhri

Oded's comments

This paper demonstrates the power of a prior result by the authors and others [CDJS15]. Using that result, it follows that if a function over $\ell$-bit strings is $\eps$-far from being unate, then $\sum_i\rho_i =\Omega(\eps)$, where $\rho_i$ is the fraction of edges in direction $i$ that violate the monotonicity (resp., anti-monotonicity) condition. Applying Levin's economical work investment strategy (see Sec 8.2.4 in my forthcoming book), the result follows.

The original abstract

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

See ECCC TR16-133.

Back to list of Oded's choices.