Boolean function analysis on high-dimensional expanders
Boolean function analysis on high-dimensional expanders
复制标题
高维展开器的布尔函数分析
DOI：
10.4230/lipics.approx-random.2018.38
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
P. Harsha
中科院分区：
文献类型：
--
作者：
Irit Dinur;Yotam Dikstein;Yuval Filmus;P. Harsha
我们开创了高维扩张器上布尔函数分析的研究。我们给出了一个基于随机游走的高维扩展的定义，它与前面关于双边链路扩展器的定义是一致的。利用这个定义，我们描述了单纯复形的布尔超立方体的傅里叶展开和傅里叶能级的模拟。我们的模拟是分解成与单纯形复形相关的随机游动的近似特征空间。我们的随机游走定义和分解还有一个额外的优势，那就是它们扩展到偏序集的更一般设置，包括高维扩展器和Grassmann偏序集，这出现在最近关于唯一博弈猜想的工作中。然后，我们利用这种分解将Friedgut-Kalai-Naor定理推广到高维展开器。我们的结果表明，恒定度高维展开器有时可以用作布尔片或超立方体的稀疏模型，并且很可能将布尔函数分析的附加结果带到这个稀疏模型上。因此，该模型可以看作是布尔片的去随机化，仅包含$$|X(k-1)|=O(N)$$
|
X
(
K
-
1
)
|
=
O
(
N
)
点数与$$\Left({\Begin{数组}{c}n\\k\end{数组}}\Right)$$
N
K
(K)切片中的点(由恰好为k个1的所有n位字符串组成)。
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 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)$$
|
X
(
k
-
1
)
|
=
O
(
n
)
points in contrast to $$\left( {\begin{array}{c}n\\ k\end{array}}\right) $$
n
k
points in the (k)-slice (which consists of all n-bit strings with exactly k ones).
DOI：
10.1109/focs.2019.00021
发表时间：
2019
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Alev, Vedat Levi;Granha Jeronimo, Fernando;Tulsiani, Madhur
通讯作者：
Tulsiani, Madhur