An Ō(n) queries adaptive tester for unateness

Subhash Khot, Igor Shinkar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016
EditorsKlaus Jansen, Claire Mathieu, Jose D. P. Rolim, Chris Umans
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770187
DOIs
StatePublished - Sep 1 2016
Event19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016 - Paris, France
Duration: Sep 7 2016Sep 9 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume60
ISSN (Print)1868-8969

Other

Other19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016
CountryFrance
CityParis
Period9/7/169/9/16

Keywords

  • Boolean Functions
  • Property Testing
  • Unateness

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'An Ō(n) queries adaptive tester for unateness'. Together they form a unique fingerprint.

Cite this