标题： 更有效的网格范数筛选及其在多党通信复杂性中的应用 显示英文标题

标题： More efficient sifting for grid norms, and applications to multiparty communication complexity

摘要： 基于近期在3项算术级数问题上取得的进展[KM'23]背后的技术，Kelley、Lovett和Meka[KLM'24]构造了第一个明确的3人函数$f:[N]^3 \rightarrow \{0,1\}$，该函数展示了随机化与（非）确定性NOF通信复杂度之间的强烈分离。 具体来说，他们的困难函数可以通过一个发送$O(1)$位的随机协议解决，但需要$\Omega(\log^{1/3}(N))$位的通信量来用确定性（或非确定性）协议解决。 我们证明了他们构造的一个更强的$\Omega(\log^{1/2}(N))$下限。 为了实现这一点，关键技术进步是对（相对密集的）二部图网格范数的筛选论证的改进。 除了定量改进外，我们在[KLM'24]的基础上通过放松难度条件实现了定性的改进：虽然[KLM'24]证明了对于满足强双边伪随机条件的任意函数$f$的下限，我们证明了一个弱单边条件就足够了。 这是通过一个新的圆柱交集结构结果（或者，在图论语言中，从三部分图中诱导出的三角形集合）实现的，该结果显示任何小的圆柱交集都可以被简单“切片”函数的总和有效地覆盖。 显示英文摘要

摘要： Building on the techniques behind the recent progress on the 3-term arithmetic progression problem [KM'23], Kelley, Lovett, and Meka [KLM'24] constructed the first explicit 3-player function $f:[N]^3 \rightarrow \{0,1\}$ that demonstrates a strong separation between randomized and (non-)deterministic NOF communication complexity. Specifically, their hard function can be solved by a randomized protocol sending $O(1)$ bits, but requires $\Omega(\log^{1/3}(N))$ bits of communication with a deterministic (or non-deterministic) protocol. We show a stronger $\Omega(\log^{1/2}(N))$ lower bound for their construction. To achieve this, the key technical advancement is an improvement to the sifting argument for grid norms of (somewhat dense) bipartite graphs. In addition to quantitative improvement, we qualitatively improve over [KLM'24] by relaxing the hardness condition: while [KLM'24] proved their lower bound for any function $f$ that satisfies a strong two-sided pseudorandom condition, we show that a weak one-sided condition suffices. This is achieved by a new structural result for cylinder intersections (or, in graph-theoretic language, the set of triangles induced from a tripartite graph), showing that any small cylinder intersection can be efficiently covered by a sum of simple ``slice'' functions.