License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.3
URN: urn:nbn:de:0030-drops-171257
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17125/
Go to the corresponding LIPIcs Volume Portal

Kaufman, Tali ; Mass, David

Double Balanced Sets in High Dimensional Expanders

pdf-format:
LIPIcs-APPROX3.pdf (0.7 MB)

Abstract

Recent works have shown that expansion of pseudorandom sets is of great importance. However, all current works on pseudorandom sets are limited only to product (or approximate product) spaces, where Fourier Analysis methods could be applied. In this work we ask the natural question whether pseudorandom sets are relevant in domains where Fourier Analysis methods cannot be applied, e.g., one-sided local spectral expanders.
We take the first step in the path of answering this question. We put forward a new definition for pseudorandom sets, which we call "double balanced sets". We demonstrate the strength of our new definition by showing that small double balanced sets in one-sided local spectral expanders have very strong expansion properties, such as unique-neighbor-like expansion. We further show that cohomologies in cosystolic expanders are double balanced, and use the newly derived strong expansion properties of double balanced sets in order to obtain an exponential improvement over the current state of the art lower bound on their minimal distance.

BibTeX - Entry

@InProceedings{kaufman_et_al:LIPIcs.APPROX/RANDOM.2022.3,
  author =	{Kaufman, Tali and Mass, David},
  title =	{{Double Balanced Sets in High Dimensional Expanders}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17125},
  URN =		{urn:nbn:de:0030-drops-171257},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.3},
  annote =	{Keywords: High dimensional expanders, Double balanced sets, Pseudorandom functions}
}

Keywords: High dimensional expanders, Double balanced sets, Pseudorandom functions
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Issue Date: 2022
Date of publication: 15.09.2022

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