Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-075 | 27th April 2018 17:36

Boolean function analysis on high-dimensional expanders

RSS-Feed




Revision #1
Authors: Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha
Accepted on: 27th April 2018 17:36
Downloads: 52
Keywords: 


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 choose k+1) points in the (k + 1)-slice (which consists of all n-bit strings with exactly k + 1 ones).


Paper:

TR18-075 | 23rd April 2018 18:43

Boolean function analysis on high-dimensional expanders





TR18-075
Authors: Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha
Publication: 23rd April 2018 18:44
Downloads: 166
Keywords: 


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 choose k+1) points in the (k + 1)-slice (which consists of all n-bit strings with exactly k + 1 ones).



ISSN 1433-8092 | Imprint