On Disperser/Lifting Properties of the Index and Inner-Product Functions
On Disperser/Lifting Properties of the Index and Inner-Product Functions
复制标题
DOI：
10.48550/arxiv.2211.17211
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
P. Beame;Sajin Koroth
中科院分区：
文献类型：
--
作者：
P. Beame;Sajin Koroth
查询到通信提升定理，它连接一个布尔函数的查询复杂性的通信复杂性的一个相关的“提升”的功能，通过组成的功能与许多副本的另一个功能称为一个小工具，已在解决许多悬而未决的问题计算复杂性。几个重要的复杂性问题可以得到解决，如果我们可以在提升索引函数所需的输入大小上做出实质性的改进，从目前的近线性大小下降到原始函数的输入数N$的多对数，或者理想情况下，常数。Lovett、Meka、Mertz、Pitassi和Zhang使用最近对向日葵引理的突破性改进来证明近线性尺寸界限，以表明与近线性尺寸的指数函数相关联的某个图是分散体。他们还提出了一个关于索引函数的猜想，这对于使用当前技术进一步改进索引提升所需的大小至关重要。本文证明了：1）当索引小工具的大小为$\log N-\omega（1）$时，Lovett等人的猜想是错误的。2)此外，满足大小为$O（\log N）$的分散器属性的内积函数，当其大小为$\log N-\omega（1）$时不具有此属性。3)尽管如此，使用索引小工具的大小至少为4，我们证明了一个提升定理的限制类的通信协议，其中一个球员是有限的发送奇偶校验的输入。4)利用这个提升定理的思想，我们得到了一个从决策树大小到奇偶决策树大小的强提升定理。我们用它来推导出一个一般的提升定理，证明复杂性从树分辨率大小到树状的$Res（\oplus）$反驳大小，这产生了许多新的指数下界这样的证明。
Query-to-communication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated `lifted' function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. Several important complexity questions could be resolved if we could make substantial improvements in the input size required for lifting with the Index function, from its current near-linear size down to polylogarithmic in the number of inputs $N$ of the original function or, ideally, constant. The near-linear size bound was shown by Lovett, Meka, Mertz, Pitassi and Zhang using a recent breakthrough improvement on the Sunflower Lemma to show that a certain graph associated with the Index function of near-linear size is a disperser. They also stated a conjecture about the Index function that is essential for further improvements in the size required for lifting with Index using current techniques. In this paper we prove the following; 1) The conjecture of Lovett et al. is false when the size of the Index gadget is $\log N-\omega(1)$. 2) Also, the Inner-Product function, which satisfies the disperser property at size $O(\log N)$, does not have this property when its size is $\log N-\omega(1)$. 3) Nonetheless, using Index gadgets of size at least 4, we prove a lifting theorem for a restricted class of communication protocols in which one of the players is limited to sending parities of its inputs. 4) Using the ideas from this lifting theorem, we derive a strong lifting theorem from decision tree size to parity decision tree size. We use this to derive a general lifting theorem in proof complexity from tree-resolution size to tree-like $Res(\oplus)$ refutation size, which yields many new exponential lower bounds on such proofs.