Influences in Product Spaces: KKL and BKKKL Revisited
Influences in Product Spaces: KKL and BKKKL Revisited
复制标题
产品空间的影响：KKL 和 BKKKL 重温
DOI：
10.1017/s0963548303005832
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
E. Friedgut
中科院分区：
文献类型：
--
作者：
E. Friedgut
变量对积空间上布尔函数的影响的概念在组合学、计算机科学等领域引起了广泛的关注。处理这一概念的两篇基本论文是Kahn， Kalai和Linial （KKL）和Bourgain， Kahn, Kalai， Katznelson和Linial （BKKKL）。在本文中，我们回顾了这些论文的结果，并提供了一些更简单的证明、更正和定理的扩展。我们提出了几个相关的开放问题。
The notion of the influence of a variable on a Boolean function on a product space has attracted much attention in combinatorics, computer science and other fields. Two of the basic papers dealing with this notion are by Kahn, Kalai and Linial (KKL) and Bourgain, Kahn, Kalai, Katznelson and Linial (BKKKL). In this paper we survey the results in those papers and offer some simpler proofs, corrections, and extensions of the theorems presented there. We present several related open problems.