Conference paper
Boolean Function Analysis on High-Dimensional Expanders
Leibniz International Proceedings in Informatics, LIPIcs, Vol.116
International Conference on Randomization and Computation (RANDOM'2018), 22 (Princeton University, New Jersey, 20/Aug/2018 - 22/Aug/2018)
Aug/2018
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 n k+1 points in the (k + 1)-slice (which consists of all n-bit strings with exactly k + 1 ones).
Details
- Title
- Boolean Function Analysis on High-Dimensional Expanders
- Creators
- Yotam Dikstein - 972WIS_INST___83Irit Dinur - 972WIS_INST___83Yuval Filmus - Technion – Israel Institute of TechnologyPrahladh Harsha - Tata Institute of Fundamental Research
- Resource Type
- Conference paper
- Publication Details
- Leibniz International Proceedings in Informatics, LIPIcs, Vol.116; Aug/2018
- Number of pages
- 20
- Publisher
- Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
- Language
- English
- DOI
- https://doi.org/10.4230/lipics.approx-random.2018.38
- Conference
- International Conference on Randomization and Computation (RANDOM'2018), 22 (Princeton University, New Jersey, 20/Aug/2018 - 22/Aug/2018)
- Grant note
- The research of the first and second authors was supported in part by Irit Dinur’s ERC-CoG grant 772839. The third author is a Taub Fellow –supported by the Taub Foundations. The research was funded by ISF grant 1337/16. The fourth author's research was supported in part by UGC–ISF grant. Part of the work was done when the author was visiting the Weizmann Institute of Science.
- Record Identifier
- 993344667403596
Metrics
26 File views/ downloads
27 Record Views