论文标题
关于索引和内部产品函数的分散器/提升特性
On Disperser/Lifting Properties of the Index and Inner-Product Functions
论文作者
论文摘要
查询对凸起的抬高定理，将布尔函数的查询复杂性连接到通过用其他称为小工具的另一个函数的副本撰写的函数获得的相关“提升”函数的通信复杂性，在计算复杂性中解决了许多开放问题。如果我们可以在索引功能上升起所需的输入大小，从当前的接近线性大小到原始功能的输入$ n $，或者理想情况下，可以解决一些重要的复杂性问题。 Lovett，Meka，Mertz，Pitassi和Zhang使用了最近的突破性改进，以表明与近线性尺寸的指数函数相关的某些图是分散剂。他们还指出了一个关于索引功能的猜想，这对于使用当前技术用索引提升所需的大小进行进一步改进至关重要。在本文中，我们证明了以下内容； 1）Lovett等人的猜想。当索引小工具的大小为$ \ log n-ω（1）$时，为false。 2）此外，在尺寸$ o（\ log n）$时满足分散属性的内部产品函数，当它的大小为$ \ log n-ω（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-ω(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-ω(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.
