文章基本信息

标题：Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality
本地全文：下载
作者：Esty Kelman ; Subhash Khot ; Guy Kindler 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-18
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.