On monotonicity testing and boolean isoperimetric-type theorems

Subhash Khot, Dor Minzer, Muli Safra

Research output: Contribution to journalArticlepeer-review


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
Issue number6
StatePublished - 2018


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

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


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

Cite this