## 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.