Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity
复制标题
近似单调布尔函数对 $O(sqrt{n})$ 查询复杂度的影响
DOI：
10.1007/978-3-642-22935-0_56
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Omri Weinstein
中科院分区：
文献类型：
--
作者：
D. Ron;R. Rubinfeld;S. Safra;Omri Weinstein
离散函数的总影响（平均灵敏度）是其基本度量之一。研究了单调布尔函数f: f0的总影响的逼近问题；1g n ！f 0;1g，我们用I[f]表示。我们提出了一种随机算法，该算法通过执行O ‘ p nlog n [f] poly(1=) ’查询，将这些函数的影响近似为（1 ' '）的倍数因子。对于这个问题，我们还证明了任意常因子近似算法的查询复杂度的下界为p n log n·I[f]]（对于I[f] =(1)），从而表明我们的算法在其对n的依赖方面几乎是最优的。对于一般函数，我们给出了一个下界为n I[f]，这与简单采样算法的复杂度相匹配。
The Total Influence (Average Sensitivity) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influe nce of a monotone Boolean function f : f0;1g n ! f 0;1g, which we denote by I[f]. We present a randomized algorithm that approximates the influence of such functions to within a multip licative factor of (1 � �) by performing O � p nlog n I[f] poly(1=�) � queries. We also prove a lower bound of � p n log n·I[f] � on the query complexity of any constant-factor approximation algorithm for this problem (which holds for I[f] = (1)), hence showing that our algorithm is almost optimal in terms of its dependence on n. For general functions we give a lower bound of � n I[f] � , which matches the complexity of a simple sampling algorithm.