License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.26
URN: urn:nbn:de:0030-drops-135657
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13565/
Go to the corresponding LIPIcs Volume Portal

Kelman, Esty ; Khot, Subhash ; Kindler, Guy ; Minzer, Dor ; Safra, Muli

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

pdf-format:
LIPIcs-ITCS-2021-26.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{kelman_et_al:LIPIcs.ITCS.2021.26,
  author =	{Esty Kelman and Subhash Khot and Guy Kindler and Dor Minzer and Muli Safra},
  title =	{{Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{James R. Lee},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13565},
  URN =		{urn:nbn:de:0030-drops-135657},
  doi =		{10.4230/LIPIcs.ITCS.2021.26},
  annote =	{Keywords: Fourier Analysis, Hypercontractivity, Log-Sobolev Inequality}
}

Keywords: Fourier Analysis, Hypercontractivity, Log-Sobolev Inequality
Collection: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Issue Date: 2021
Date of publication: 04.02.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI