






















Building on the techniques behind the recent progress on the 3-term arithmetic progression problem \cite{KelleyM2023strong}, Kelley, Lovett, and Meka \cite{KelleyLM2024-nof} 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 $Ω(\log^{1/3}(N))$ bits of communication with a deterministic (or non-deterministic) protocol. We show a stronger $Ω(\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 \cite{KelleyLM2024-nof} by relaxing the hardness condition: while \cite{KelleyLM2024-nof} 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。