论文标题
朝着对数符号的猜想更强大的反例
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
论文作者
论文摘要
我们为对数及量的猜想的查询复杂性类似物提供了改进的分离。这对Chattopadhyay，Mande和Sherif（JACM '20）的最新工作都改善了（在设计大量示例方面）和定量（从四分之一到立方体提高了差距）。我们打开一个问题，即证明了示例的XOR组成的随机通信复杂性下限。线性下限将导致对数及阵列猜想的新和改进的反驳。此外，如果这些组合中的任何一个甚至具有亚线性成本的随机通信协议，它将证明随机奇偶校验决策树的复杂性一般不会提高到随机通信复杂性（带有XOR小工具）。
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $Θ(n)$. This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM '20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
