Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

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

RSS-Feed




Revision #1
Authors: C. Seshadhri, Deeparnab Chakrabarty
Accepted on: 2nd September 2016 23:32
Downloads: 968
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
Authors: C. Seshadhri, Deeparnab Chakrabarty
Publication: 25th August 2016 11:47
Downloads: 1607
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.



ISSN 1433-8092 | Imprint