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

preprint2016arXivOpen access

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 \to \{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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Write a reviewWrite

No reviews yet.

Add a commentWrite

No comments yet.

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

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0

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

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0

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