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.ISAAC.2021.56
URN: urn:nbn:de:0030-drops-154898
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15489/
Kaufman, Tali ;
Mass, David
Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion
Abstract
In recent years, high dimensional expanders have been found to have a variety of applications in theoretical computer science, such as efficient CSPs approximations, improved sampling and list-decoding algorithms, and more. Within that, an important high dimensional expansion notion is cosystolic expansion, which has found applications in the construction of efficiently decodable quantum codes and in proving lower bounds for CSPs.
Cosystolic expansion is considered with systems of equations over a group where the variables and equations correspond to faces of the complex. Previous works that studied cosystolic expansion were tailored to the specific group ?₂. In particular, Kaufman, Kazhdan and Lubotzky (FOCS 2014), and Evra and Kaufman (STOC 2016) in their breakthrough works, who solved a famous open question of Gromov, have studied a notion which we term "parity" expansion for small sets. They showed that small sets of k-faces have proportionally many (k+1)-faces that contain an odd number of k-faces from the set. Parity expansion for small sets could then be used to imply cosystolic expansion only over ?₂.
In this work we introduce a stronger unique-neighbor-like expansion for small sets. We show that small sets of k-faces have proportionally many (k+1)-faces that contain exactly one k-face from the set. This notion is fundamentally stronger than parity expansion and cannot be implied by previous works.
We then show, utilizing the new unique-neighbor-like expansion notion introduced in this work, that cosystolic expansion can be made group-independent, i.e., unique-neighbor-like expansion for small sets implies cosystolic expansion over any group.
BibTeX - Entry
@InProceedings{kaufman_et_al:LIPIcs.ISAAC.2021.56,
author = {Kaufman, Tali and Mass, David},
title = {{Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {56:1--56:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15489},
URN = {urn:nbn:de:0030-drops-154898},
doi = {10.4230/LIPIcs.ISAAC.2021.56},
annote = {Keywords: High dimensional expanders, Unique-neighbor-like expansion, Cosystolic expansion}
}
|
Keywords: |
|
High dimensional expanders, Unique-neighbor-like expansion, Cosystolic expansion |
|
Collection: |
|
32nd International Symposium on Algorithms and Computation (ISAAC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.11.2021 |
