ECCC-Report TR18-075https://eccc.weizmann.ac.il/report/2018/075Comments and Revisions published for TR18-075en-usWed, 26 Jan 2022 10:54:58 +0200
Revision 3
| Boolean function analysis on high-dimensional expanders |
Irit Dinur,
Yuval Filmus,
Prahladh Harsha,
Yotam Dikstein
https://eccc.weizmann.ac.il/report/2018/075#revision3We initiate the study of Boolean function analysis on high-dimensional expanders. We give a random-walk based definition of high-dimensional expansion, which coincides with the earlier definition in terms of two-sided link expanders. Using this definition, we describe an analog of the Fourier expansion and the Fourier levels of the Boolean hypercube for simplicial complexes. Our analog is a decomposition into approximate eigenspaces of random walks associated with the simplicial complexes. Our random-walk definition and the decomposition have the additional advantage that they extend to the more general setting of posets, encompassing both high-dimensional expanders and the Grassmann poset, which appears in recent work on the unique games conjecture.
We then use this decomposition to extend the Friedgut-Kalai-Naor theorem to high-dimensional expanders. Our results demonstrate that a constant-degree high-dimensional expander 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 only $|X(k ? 1)| = O(n)$ points in contrast to $\binom{n}{k}$ points in the $k$-slice (which consists of all $n$-bit strings with exactly $k$ ones).Wed, 26 Jan 2022 10:54:58 +0200https://eccc.weizmann.ac.il/report/2018/075#revision3
Revision 2
| Boolean function analysis on high-dimensional expanders |
Irit Dinur,
Yuval Filmus,
Prahladh Harsha,
Yotam Dikstein
https://eccc.weizmann.ac.il/report/2018/075#revision2We initiate the study of Boolean function analysis on high-dimensional expanders. We give a random-walk based definition of high dimensional expansion, which coincides with the earlier definition in terms of two-sided link expanders. Using this definition, we describe an analogue of the Fourier expansion and the Fourier levels of the Boolean hypercube for simplicial complexes. Our analogue is a decomposition into approximate eigenspaces of random walks associated with the simplicial complexes. We then use this decomposition to extend the Friedgut-Kalai-Naor theorem to high-dimensional expanders.
Our results demonstrate that a high-dimensional expander 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 only |X(k-1)|=O(n) points in contrast to \binom{n}{k} points in the (k)-slice (which consists of all n-bit strings with exactly k ones).
Our random-walk definition and the decomposition has the additional advantage that they extend to the more general setting of posets, which include both high-dimensional expanders and the Grassmann poset, which appears in recent works on the unique games conjecture. Tue, 29 Jan 2019 15:56:43 +0200https://eccc.weizmann.ac.il/report/2018/075#revision2
Revision 1
| Boolean function analysis on high-dimensional expanders |
Yotam Dikstein,
Irit Dinur,
Yuval Filmus,
Prahladh Harsha
https://eccc.weizmann.ac.il/report/2018/075#revision1We 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).Fri, 27 Apr 2018 17:36:44 +0300https://eccc.weizmann.ac.il/report/2018/075#revision1
Paper TR18-075
| Boolean function analysis on high-dimensional expanders |
Irit Dinur,
Yuval Filmus,
Prahladh Harsha,
Yotam Dikstein
https://eccc.weizmann.ac.il/report/2018/075We 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).Mon, 23 Apr 2018 18:44:48 +0300https://eccc.weizmann.ac.il/report/2018/075