@inproceedings{c227727a33c44654b5aca5f55008bfd9,
title = "Theorems of KKL, friedgut, and talagrand via random restrictions and log-sobolev inequality",
abstract = "We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL Theorem, Friedgut{\textquoteright}s Junta Theorem, and Talagrand{\textquoteright}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.",
keywords = "Fourier analysis, Hypercontractivity, Log-sobolev inequality",
author = "Esty Kelman and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra",
note = "Funding Information: Funding Esty Kelman: Supported by the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (Grant agreement No. 835152). Subhash Khot: Supported by the NSF Award CCF-1422159, the Simons Collaboration on Algorithms and Geometry, and the Simons Investigator Award. Muli Safra: Supported by the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (Grant agreement No. 835152). Publisher Copyright: {\textcopyright} Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra.; 12th Innovations in Theoretical Computer Science Conference, ITCS 2021 ; Conference date: 06-01-2021 Through 08-01-2021",
year = "2021",
month = feb,
day = "1",
doi = "10.4230/LIPIcs.ITCS.2021.26",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Lee, {James R.}",
booktitle = "12th Innovations in Theoretical Computer Science Conference, ITCS 2021",
}