Log-rank and lifting for AND-functions
Log-rank and lifting for AND-functions
复制标题
AND 函数的对数排序和提升
DOI：
10.1145/3406325.3450999
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Yuan, Weiqiang
中科院分区：
文献类型：
--
作者：
Knop, Alexander;Lovett, Shachar;McGuire, Sam;Yuan, Weiqiang
设f：{0，1}n→ {0，1}是一个布尔函数，并且letf（x，y）=f（x y）表示AND函数off，其中x y表示逐位AND。我们研究的确定性通信复杂性关闭的，并表明，到一个logn因子，它是有界的多项式在对数的通信矩阵关闭的真实的秩。这是在一个logn因子内建立对数秩猜想的AND-函数，而没有任何限制。我们的结果与以往的结果相比，对数秩猜想的特殊情况下，需要显着的限制f，如单调性或低F2-度。我们的技术也可以用来证明（在一个logn因子）alifting定理的AND-功能，说明确定性的通信复杂性关闭的是多项式相关的AND-决策树的复杂性关闭。结果依赖于一个新的结构性的结果，布尔函数sf：{0，1}n→ {0，1}与稀疏多项式表示，这可能是独立的利益。我们表明，如果多项式computingf有几个单项式，那么单项式的集合系统有一个小的命中集，其稀疏性的大小poly-logarithmic。我们还建立了这个结果的推广到多线性多项式sf：{0，1}n→具有更大的范围。
Letf: {0, 1}n→ {0, 1} be a boolean function, and letf∧(x,y) =f(x∧y) denote theAND-functionoff, wherex∧ydenotes bit-wise AND. We study the deterministic communication complexity off∧and show that, up to a lognfactor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix off∧. This comes within a lognfactor of establishing the log-rank conjecture for AND-functions withno assumptionsonf. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions onfsuch as monotonicity or low F2-degree. Our techniques can also be used to prove (within a lognfactor) alifting theoremfor AND-functions, stating that the deterministic communication complexity off∧is polynomially related to theAND-decision tree complexityoff.The results rely on a new structural result regarding boolean functionsf: {0, 1}n→ {0, 1} with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computingfhas few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomialsf: {0, 1}n→ with a larger range.
登录
查看更多内容
影响因子：
1.4
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas
DOI：
10.26421/qic10.5-6-5
发表时间：
2009-06
期刊：
ArXiv
影响因子：
--
作者：
Alexander A. Sherstov
通讯作者：
Alexander A. Sherstov
单调 NC 层次结构的分离
影响因子：
1.1
作者：
R. Raz;P. McKenzie
通讯作者：
P. McKenzie
DOI：
10.1145/2591796.2591838
发表时间：
2013-11
期刊：
Proceedings of the forty-sixth annual ACM symposium on Theory of computing
影响因子：
--
作者：
Mika Göös;T. Pitassi
通讯作者：
Mika Göös;T. Pitassi
使用内积将 BPP 的查询提升为通信
DOI：
10.4230/lipics.icalp.2019.35
发表时间：
2019
期刊：
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
A. Chattopadhyay;Yuval Filmus;Sajin Koroth;Or Meir;T. Pitassi
通讯作者：
T. Pitassi