On Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality

A new publication by our team in ECCC (Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra), in which alternate proofs for three related results in analysis of Boolean functions are given, namely the KKL Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. It follows a new approach: looking at the first Fourier level of the function after a suitable random restriction and applying the Log-Sobolev inequality appropriately. In particular, it avoids using the hypercontractive inequality

that is common to the original proofs. Our proofs might serve as an alternate, uniform exposition to these theorems and the techniques might benefit further research.