solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看10163次
Boolean functions on high-dimensional expanders. (arXiv:1804.08155v3 [cs.CC] UPDATED)
来源于:arXiv
We 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 查看全文>>