On Monotonicity Testing and Boolean Isoperimetric Type Theorems

Subhash Khot, Dor Minzer, Muli Safra

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

Abstract

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we give a monotonicity testing algorithm that makes, up to polylog factors, (square root of n)/∈2 non-adaptive queries to a function f:0, 1n -> 0, 1, always accepts a monotone function and rejects a function that is ∈-far from being monotone with constant probability.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PublisherIEEE Computer Society
Pages52-58
Number of pages7
ISBN (Electronic)9781467381918
DOIs
StatePublished - Dec 11 2015
Event56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States
Duration: Oct 17 2015Oct 20 2015

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2015-December
ISSN (Print)0272-5428

Other

Other56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
CountryUnited States
CityBerkeley
Period10/17/1510/20/15

Keywords

  • Boolean functions
  • isoperimetry
  • monotone functions
  • property testing

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'On Monotonicity Testing and Boolean Isoperimetric Type Theorems'. Together they form a unique fingerprint.

Cite this