# Testing Unateness Nearly Optimally

arXiv: https://arxiv.org/abs/1904.05309 · HTML: https://mlsanity.com/paper/1904.05309/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Apr 2019.

## Built on by (most cited first, 1 of 1)

- [Agnostic proper learning of monotone functions: beyond the black-box correction barrier](https://mlsanity.com/paper/2304.02700/) (2023)

## Abstract (arXiv)

We present an tildeO(n2/3/ε2)-query algorithm that tests whether an unknown Boolean function fcolon0,1nrightarrow 0,1 is unate (i.e., every variable is either non-decreasing or non-increasing) or ε-far from unate. The upper bound is nearly optimal given the tildeOmega(n2/3) lower~bound of [CWX17a]. The algorithm builds on a novel use of the binary search procedure and its analysis over long random paths.