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

C. Seshadhri; Deeparnab Chakrabarty

arxiv: 1608.06980 · v2 · pith:SJ3UTCLLnew · submitted 2016-08-24 · 💻 cs.DS · cs.DM

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

Deeparnab Chakrabarty , C. Seshadhri This is my paper

classification 💻 cs.DS cs.DM

keywords testerunatenessvarepsilondescribefunctionsnon-adaptivequeryadaptive

0 comments

read the original 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 \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.

This paper has not been read by Pith yet.

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

discussion (0)