Influences in Product Spaces: KKL and BKKKL Revisited
Ehud Friedgut · Combinatorics Probability Computing · 2004
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.