Testing Unateness of Real-Valued Functions

Abstract

We give a unateness tester for functions of the form $f:[n{]}^d\to R$, where $n,d\in \mathbb{N}$ and $R\subseteq \mathbb{R}$ with query complexity $O(\frac{d\log (\max (d,n))}{\epsilon })$. Previously known unateness testers work only for Boolean functions over the domain $\{0,1{\}}^d$. We show that every unateness tester for real-valued functions over hypergrid has query complexity $\Omega (\min \{d,|R{|}^2\})$. Consequently, our tester is nearly optimal for real-valued functions over $\{0,1{\}}^d$. We also prove that every nonadaptive, 1-sided error unateness tester for Boolean functions needs $\Omega (\sqrt{d}/\epsilon )$ queries. Previously, no lower bounds for testing unateness were known.

References in corpus (1)

• New algorithms and lower bounds for monotonicity testing

Cited by in corpus (2)

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