Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-009 | 6th February 2020 23:00

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

RSS-Feed




TR20-009
Authors: Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
Publication: 6th February 2020 23:02
Downloads: 2770
Keywords: 


Abstract:

We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL
Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. We follow 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, we avoid 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.



ISSN 1433-8092 | Imprint