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

Dikstein, Yotam ; Dinur, Irit ; Filmus, Yuval ; Harsha, Prahladh

Boolean Function Analysis on High-Dimensional Expanders

pdf-format:
LIPIcs-APPROX-RANDOM-2018-38.pdf (0.5 MB)

Abstract

We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders.
Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse model for the Boolean slice or hypercube, and quite possibly additional results from Boolean function analysis can be carried over to this sparse model. Therefore, this model can be viewed as a derandomization of the Boolean slice, containing |X(k)|=O(n) points in comparison to binom{n}{k+1} points in the (k+1)-slice (which consists of all n-bit strings with exactly k+1 ones).

BibTeX - Entry

@InProceedings{dikstein_et_al:LIPIcs:2018:9442,
  author =	{Yotam Dikstein and Irit Dinur and Yuval Filmus and Prahladh Harsha},
  title =	{{Boolean Function Analysis on High-Dimensional Expanders}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9442},
  URN =		{urn:nbn:de:0030-drops-94421},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.38},
  annote =	{Keywords: high dimensional expanders, Boolean function analysis, sparse model}
}

Keywords: high dimensional expanders, Boolean function analysis, sparse model
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

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