Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR16-133 | 2nd September 2016 23:32

#### A $\widetilde{O}(n)$ Non-Adaptive Tester for Unateness

Revision #1
Accepted on: 2nd September 2016 23:32
Keywords:

Abstract:

Khot and Shinkar (RANDOM, 2016) recently describe an adaptive, $O(n\log(n)/\varepsilon)$-query tester for unateness of Boolean functions $f:\{0,1\}^n \mapsto \{0,1\}$. In this note we describe a simple non-adaptive, $O(n\log(n/\varepsilon)/\varepsilon)$ -query tester for unateness for functions over the hypercube with any ordered range.

Changes to previous version:

As suggested by Oded Goldreich, we mention that our proof is essentially an implementation of Levin's investment strategy.

### Paper:

TR16-133 | 25th August 2016 00:15

#### A $\widetilde{O}(n)$ Non-Adaptive Tester for Unateness

TR16-133
Khot and Shinkar (RANDOM, 2016) recently describe an adaptive, $O(n\log(n)/\varepsilon)$-query tester for unateness of Boolean functions $f:\{0,1\}^n \mapsto \{0,1\}$. In this note we describe a simple non-adaptive, $O(n\log(n/\varepsilon)/\varepsilon)$ -query tester for unateness for functions over the hypercube with any ordered range.