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.2019.34
URN: urn:nbn:de:0030-drops-101279
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10127/
Go to the corresponding LIPIcs Volume Portal

Filmus, Yuval ; O'Donnell, Ryan ; Wu, Xinyu

A Log-Sobolev Inequality for the Multislice, with Applications

pdf-format:
LIPIcs-ITCS-2019-34.pdf (0.5 MB)

Abstract

Let kappa in N_+^l satisfy kappa_1 + *s + kappa_l = n, and let U_kappa denote the multislice of all strings u in [l]^n having exactly kappa_i coordinates equal to i, for all i in [l]. Consider the Markov chain on U_kappa where a step is a random transposition of two coordinates of u. We show that the log-Sobolev constant rho_kappa for the chain satisfies rho_kappa^{-1} <= n * sum_{i=1}^l 1/2 log_2(4n/kappa_i), which is sharp up to constants whenever l is constant. From this, we derive some consequences for small-set expansion and isoperimetry in the multislice, including a KKL Theorem, a Kruskal - Katona Theorem for the multislice, a Friedgut Junta Theorem, and a Nisan - Szegedy Theorem.

BibTeX - Entry

@InProceedings{filmus_et_al:LIPIcs:2018:10127,
  author =	{Yuval Filmus and Ryan O'Donnell and Xinyu Wu},
  title =	{{A Log-Sobolev Inequality for the Multislice, with Applications}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{34:1--34:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10127},
  URN =		{urn:nbn:de:0030-drops-101279},
  doi =		{10.4230/LIPIcs.ITCS.2019.34},
  annote =	{Keywords: log-Sobolev inequality, small-set expansion, conductance, hypercontractivity, Fourier analysis, representation theory, Markov chains, combinatorics}
}

Keywords: log-Sobolev inequality, small-set expansion, conductance, hypercontractivity, Fourier analysis, representation theory, Markov chains, combinatorics
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

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