2026-08-17T06:33:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13565 2024-03-06T10:52:19Z ddc:004 open_access

Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality Kelman, Esty Khot, Subhash Kindler, Guy Minzer, Dor Safra, Muli Fourier Analysis Hypercontractivity Log-Sobolev Inequality 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Esty Kelman and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.26 urn:nbn:de:0030-drops-135657 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.26 eng https://creativecommons.org/licenses/by/3.0/legalcode