Volume 16 (2020) Article 3 pp. 1-36

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

by Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri

Received: June 25, 2018
Revised: July 2, 2020
Published: September 16, 2020

$\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

DOI: 10.4086/toc.2020.v016a003

© 2020 Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri
Licensed under a Creative Commons Attribution License (CC-BY)