2026-07-23T08:19:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9442 2024-03-12T11:57:38Z ddc:004 open_access

Boolean Function Analysis on High-Dimensional Expanders Dikstein, Yotam Dinur, Irit Filmus, Yuval Harsha, Prahladh high dimensional expanders Boolean function analysis sparse model 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yotam Dikstein and Irit Dinur and Yuval Filmus and Prahladh Harsha 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.38 urn:nbn:de:0030-drops-94421 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.38 eng https://creativecommons.org/licenses/by/3.0/legalcode