On monotonicity testing and boolean isoperimetric-type theorems

Subhash Khot, Dor Minzer, Muli Safra

Research output: Contribution to journalArticle

Abstract

We show a directed and robust analogue of a boolean isoperimetric-type theorem of Talagrand [Geom. Funct. Anal., 3 (1993), pp. 295-314]. As an application, we give a monotonicity testing algorithm that makes Õ(√n/ε 2 ) nonadaptive queries to a function f : {0, 1} n 7→ {0, 1}, always accepts a monotone function, and rejects a function that is ε-far from being monotone with constant probability.

Original languageEnglish (US)
Pages (from-to)2238-2276
Number of pages39
JournalSIAM Journal on Computing
Volume47
Issue number6
DOIs
StatePublished - 2018

Keywords

  • Boolean functions
  • Boolean isoperimetry
  • Monotonicity testing
  • Property testing

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'On monotonicity testing and boolean isoperimetric-type theorems'. Together they form a unique fingerprint.

  • Cite this