On Monotonicity Testing and Boolean Isoperimetric Type Theorems
On Monotonicity Testing and Boolean Isoperimetric Type Theorems
复制标题
关于单调性测试和布尔等周类型定理
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Safra
中科院分区：
文献类型：
--
作者：
Subhash Khot;Dor Minzer;S. Safra
我们展示了 Talagrand 布尔等周型定理的有向且稳健的类似物 [13]。作为一个应用，我们给出了一种单调性测试算法，该算法使 O̅(√n/ε<sup>2</sup>) 对函数 f 进行非自适应查询：{0, 1}<sup>n</sup> → {0, 1}，始终接受单调函数并以恒定概率拒绝 ε-远离单调的函数。
We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand [13]. As an application, we give a monotonicity testing algorithm that makes O̅(√n/ε<sup>2</sup>) non-adaptive queries to a function f : {0, 1}<sup>n</sup> → {0, 1}, always accepts a monotone function and rejects a function that is ε-far from being monotone with constant probability.