@inproceedings{bb506233170b4b0a80eb2eb3d14b876c,
title = "On Monotonicity Testing and Boolean Isoperimetric Type Theorems",
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.",
keywords = "Boolean functions, isoperimetry, monotone functions, property testing",
author = "Subhash Khot and Dor Minzer and Muli Safra",
year = "2015",
month = dec,
day = "11",
doi = "10.1109/FOCS.2015.13",
language = "English (US)",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "52--58",
booktitle = "Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015",
note = "56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 ; Conference date: 17-10-2015 Through 20-10-2015",
}