Theory of Computing
-------------------
Title     : Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps
Authors   : Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri
Volume    : 16
Number    : 3
Pages     : 1-36
URL       : https://theoryofcomputing.org/articles/v016a003

Abstract
--------
$ \newcommand{\R}{{\mathbb R}} \newcommand{\ensuremath}[1]{#1}
\newcommand{\eps}{\varepsilon}
\newcommand{\ord}[2][th]{\ensuremath{{#2}^{\mathrm{#1}}}} $

We study the problem of testing unateness of functions $f:\{0,1\}^d
\to \R$. A function $f:\{0,1\}^d \to \R$ is _unate_ if for every
coordinate $i\in [d]$, the function is either nonincreasing in the
$\ord{i}$ coordinate or nondecreasing in the $\ord{i}$ coordinate. We
give an $O((d/\eps) \cdot \log(d/\eps))$-query nonadaptive tester and
an $O(d/\eps)$-query adaptive tester and show that both testers are
optimal for a fixed distance parameter $\eps$. Previously known
unateness testers worked only for Boolean functions, and their query
complexity had worse dependence on the dimension $d$ both for the
adaptive and the nonadaptive case. Moreover, no lower bounds for
testing unateness were known. (Concurrent work by Chen et al.
(STOC'17) proved an $\Omega(d/\log^2 d)$ lower bound on the
nonadaptive query complexity of testing unateness of Boolean
functions.) We also generalize our results to obtain optimal unateness
testers for functions $f:[n]^d\to\R$.

Our results establish that adaptivity helps with testing unateness of
real-valued functions on domains of the form $\{0,1\}^d$ and, more
generally, $[n]^d$. This stands in contrast to the situation for
monotonicity testing where, as shown by Chakrabarty and Seshadhri
(Theory of Computing, 2014), there is no adaptivity gap for functions
$f:[n]^d\to\R$.

---------------------

An extended abstract of this paper appeared in the Proceedings of the
44th International Colloquium on Automata, Languages, and Programming
(ICALP), 2017.