Boolean Functions With Low Average Sensitivity Depend On Few Coordinates
Boolean Functions With Low Average Sensitivity Depend On Few Coordinates
复制标题
平均灵敏度较低的布尔函数依赖于很少的坐标
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
E. Friedgut
中科院分区：
文献类型：
--
作者：
E. Friedgut
。一个点的敏感性是区域，即离散立方体值所在的离散点中点的邻居数。平均灵敏度是所有点的灵敏度的平均值。 （这也可以解释为变量上的影响的总和，也可以解释为集合的边缘边界的量度，这是。通过函数取决于坐标，仅在近似值的准确性但不取决于次数的情况下，恒定是一个恒定的。我们还提出了该定理的更通用的版本，其中敏感性是相对于一个不是立方体上均匀度量的产品度量测量的。
. The sensitivity of a point is dist, i.e. the number of neighbors of the point in the discrete cube on which the value of differs. The average sensitivity of is the average of the sensitivity of all points in . (This can also be interpreted as the sum of the influences of the variables on , or as a measure of the edge boundary of the set which is the characteristic function of.) We show here that if the average sensitivity of is then can be approximated by a function depending on coordinates where is a constant depending only on the accuracy of the approximation but not on . We also present a more general version of this theorem, where the sensitivity is measured with respect to a product measure which is not the uniform measure on the cube.