Boolean functions on high-dimensional expanders
Preprint
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).
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRYForum of Mathematics, Sigma, 2017
- High Dimensional Expanders Imply Agreement Expanders2017
- Making the Long Code ShorterSIAM Journal on Computing, 2015
- Ramanujan Complexes and Bounded Degree Topological Expanders2014
- A quasi-stability result for dictatorships in S nCombinatorica, 2014
- A stability result for balanced dictatorships in SnRandom Structures & Algorithms, 2013
- KKL, Kruskal--Katona, and Monotone NetsSIAM Journal on Computing, 2013
- Ramanujan complexes of typeà dIsrael Journal of Mathematics, 2005
- Explicit constructions of Ramanujan complexes of typeEuropean Journal of Combinatorics, 2005
- Boolean functions whose Fourier transform is concentrated on the first two levelsAdvances in Applied Mathematics, 2002