Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor +2

We study the problem of testing unateness of functions $f:\{0,1{\}}^d\to \mathbb{R}.$ We give a $O(\frac{d}{\epsilon }\cdot \log \frac{d}{\epsilon })$-query nonadaptive tester and a $O(\frac{d}{\epsilon })$-quer…