@inproceedings{4f8a378c3038488c9eb5c54dc6d49745,
title = "An Ō(n) queries adaptive tester for unateness",
abstract = "We present an adaptive tester for the unateness property of Boolean functions. Given a function f : {0, 1}n → {0, 1} the tester makes O(n log(n)/ϵ) adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 if a function is ϵ-far from being unate.",
keywords = "Boolean Functions, Property Testing, Unateness",
author = "Subhash Khot and Igor Shinkar",
note = "Funding Information: Research supported by NSF grants CCF 1422159, 1061938, 0832795; 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016 ; Conference date: 07-09-2016 Through 09-09-2016",
year = "2016",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.APPROX-RANDOM.2016.37",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Klaus Jansen and Claire Mathieu and Rolim, {Jose D. P.} and Chris Umans",
booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016",
}