Abstract:We construct a point-line incidence problem over the reals whose randomized communication complexity is constant, but whose deterministic communication complexity is linear even when the players have access to an equality oracle. This is the strongest possible separation between these two measures, and it improves on an earlier $O(1)$-versus-$\Omega(\sqrt{n})$ separation of Göös, Harms, and Riazanov.
Because point-line incidence problems have constant sign rank, our construction also bears on a question of Harms and Zamaraev, who asked whether constant sign rank together with constant randomized communication complexity forces constant equality-oracle complexity. This was already refuted by Göös, Harms, Imbach, and Sokolov with a logarithmic lower bound; our example improves the separation to linear, which is optimal.
The proof draws on a construction in the recent disproof of the sum-product conjecture over the reals by Bloom, Sawin, Schildkraut, and Zhelezov, using totally real number fields of large degree and small discriminant.
From: Marcel Goh [view email]
[v1]
Tue, 23 Jun 2026 21:35:18 UTC (19 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。