Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-126 | 8th August 2016 16:55

An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness

RSS-Feed




TR16-126
Authors: Subhash Khot, Igor Shinkar
Publication: 12th August 2016 11:57
Downloads: 1247
Keywords: 


Abstract:

We present an adaptive tester for the unateness property of Boolean functions. Given a function $f:\{0,1\}^n \to \{0,1\}$ the tester makes $O(n \log(n)/\epsilon)$ adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 any function that is $\epsilon$-far from being unate.



ISSN 1433-8092 | Imprint