Boolean function monotonicity testing requires (almost) n1/2 non-adaptive queries

Xi Chen, Anindya De, Rocco A. Servedio, Li Yang Tan

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

30 Scopus citations

Abstract

We prove a lower bound of Ω(n1/2-c), for all c > 0, on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an n-variable Boolean function is monotone versus constant-far from monotone. This improves a Ω(n 1/5 ) lower bound for the same problem that was obtained in [6], and is very close to the recent upper bound of Õ(n1/22 ) by Khot et al. [13].

Original languageEnglish (US)
Title of host publicationSTOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages519-528
Number of pages10
ISBN (Electronic)9781450335362
DOIs
StatePublished - Jun 14 2015
Event47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States
Duration: Jun 14 2015Jun 17 2015

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume14-17-June-2015
ISSN (Print)0737-8017

Other

Other47th Annual ACM Symposium on Theory of Computing, STOC 2015
CountryUnited States
CityPortland
Period6/14/156/17/15

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Boolean function monotonicity testing requires (almost) n<sup>1/2</sup> non-adaptive queries'. Together they form a unique fingerprint.

Cite this