pith. sign in

arxiv: 2606.25192 · v1 · pith:TBWRXMIJnew · submitted 2026-06-23 · 💻 cs.CC

Communication complexity of point-line incidences over the reals

Marcel K. Goh , Hamed Hatami This is my paper

Pith reviewed 2026-06-25 21:18 UTC · model grok-4.3

classification 💻 cs.CC
keywords communication complexitypoint-line incidencesrandomized communicationdeterministic communicationequality oraclesign ranksum-product conjecture
0
0 comments X

The pith

A point-line incidence problem over the reals has constant randomized communication complexity but linear deterministic complexity even with an equality oracle.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors construct a point-line incidence problem over the reals in which randomized communication complexity is constant. In contrast, the deterministic communication complexity is linear, and this holds even when the communicating parties have access to an equality oracle. This provides the strongest possible separation between randomized and deterministic communication complexity for this type of problem. The result also gives an optimal separation for a question about whether constant sign rank and constant randomized complexity imply constant equality-oracle complexity. The construction is based on algebraic objects arising from the disproof of the sum-product conjecture over the reals.

Core claim

There exists 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 obtained by using totally real number fields of large degree and small discriminant to define the points and lines in a way that creates the desired complexity gap in the communication matrix.

What carries the argument

The point-line incidence instance constructed from totally real number fields of large degree and small discriminant, which yields a communication matrix with constant randomized complexity but linear deterministic complexity under equality oracle.

If this is right

  • Constant sign rank combined with constant randomized communication complexity does not force constant equality-oracle complexity.
  • The gap between randomized and deterministic communication complexity can be made linear for geometric incidence problems.
  • The algebraic techniques from the sum-product conjecture disproof over the reals can be adapted to separate communication complexity measures.
  • Prior separations of O(1) versus Omega(sqrt(n)) are strengthened to a linear gap.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar number field constructions might produce hard instances for other communication problems involving geometric objects.
  • The result suggests that deterministic protocols cannot efficiently handle certain algebraic incidence structures even with equality tests.
  • Extensions to higher-dimensional incidences or other fields could yield further separations in communication models.

Load-bearing premise

The algebraic construction using number fields produces incidence problems with the claimed gap in communication complexities.

What would settle it

A deterministic communication protocol with sublinear communication cost for the constructed incidence problem, even when allowed an equality oracle, would falsify the linear lower bound.

read the original 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\"o\"os, 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\"o\"os, 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper constructs a point-line incidence problem over the reals with constant randomized communication complexity but linear deterministic communication complexity even under an equality oracle. This yields the strongest possible separation between these measures, improves on the prior O(1)-vs-Ω(√n) gap of Göös-Harms-Riazanov, and refutes a question of Harms-Zamaraev by showing that constant sign rank plus constant randomized CC need not imply constant equality-oracle complexity. The construction is obtained by importing an algebraic object from the Bloom-Sawin-Schildkraut-Zhelezov disproof of the real sum-product conjecture that uses totally real fields of large degree and small discriminant.

Significance. If the central claim holds, the result supplies an optimal linear separation for incidence problems and gives a strong negative answer to the Harms-Zamaraev question. The explicit use of the BSSZ algebraic construction is a methodological strength, as it imports a parameter-free high-degree object whose incidence matrix is then shown to have the desired communication properties.

major comments (1)
  1. [Section describing the randomized protocol and its cost analysis (the reduction from the BSSZ object)] The randomized upper bound is load-bearing for the constant-vs-linear separation. The manuscript must supply an explicit protocol (e.g., random linear combinations or fingerprinting over the field) together with a communication-cost analysis showing that the cost remains O(1) and independent of the field degree; without this, the claim that the BSSZ-derived incidence matrix admits constant randomized CC is not yet verified.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need for greater explicitness in the randomized protocol section. We address the comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Section describing the randomized protocol and its cost analysis (the reduction from the BSSZ object)] The randomized upper bound is load-bearing for the constant-vs-linear separation. The manuscript must supply an explicit protocol (e.g., random linear combinations or fingerprinting over the field) together with a communication-cost analysis showing that the cost remains O(1) and independent of the field degree; without this, the claim that the BSSZ-derived incidence matrix admits constant randomized CC is not yet verified.

    Authors: We agree that the current description of the randomized protocol is insufficiently explicit. In the revised manuscript we will add a dedicated subsection that spells out the protocol: the two parties sample a short random vector of coefficients from a small finite subset of the totally real field (using the small-discriminant guarantee from the BSSZ construction) and exchange the resulting linear combinations; incidence is declared if the evaluated inner product is zero. We will include a self-contained error-probability analysis showing that a constant number of repetitions suffices to drive the error below 1/3 independently of the field degree, because the discriminant bound controls the number of roots of the relevant polynomials. This addition will make the constant randomized communication complexity claim fully verifiable. revision: yes

Circularity Check

0 steps flagged

No circularity: external algebraic construction imported from independent prior work.

full rationale

The paper's central claim is a construction of a point-line incidence instance drawn from the Bloom-Sawin-Schildkraut-Zhelezov disproof of the sum-product conjecture (distinct authors). No equations, definitions, or arguments in the provided abstract or description reduce the claimed randomized-vs-deterministic separation back to a fitted parameter, self-referential definition, or load-bearing self-citation chain. The derivation relies on external algebraic structure rather than renaming or re-deriving its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract; the proof is said to draw on an external algebraic construction whose precise properties for communication complexity are not visible here.

axioms (1)
  • domain assumption The point-line incidence matrix derived from totally real number fields of large degree and small discriminant (Bloom et al.) has constant randomized communication complexity and linear deterministic communication complexity even with equality oracle.
    The abstract states that the proof draws on this construction to obtain the claimed separation.

pith-pipeline@v0.9.1-grok · 5712 in / 1254 out tokens · 25730 ms · 2026-06-25T21:18:03.723365+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 2 linked inside Pith

  1. [1]

    ``Complexity classes in communication complexity theory.'' In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (1986), 337--347

    L\'aszl\'o Babai, P\'eter Frankl, and J\'anos Simon. ``Complexity classes in communication complexity theory.'' In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (1986), 337--347

    1986

  2. [2]

    Factorization norms and an inverse theorem for MaxCut

    Igor Balla, Lianna Hambardzumyan, and Istv\'an Tomon. Factorization norms and an inverse theorem for MaxCut. arXiv:2506.23989 (2025), 23 pp

    arXiv 2025

  3. [3]

    Bloom, Will Sawin, Carl Schildkraut, and Dmitrii Zhelezov

    Thomas F. Bloom, Will Sawin, Carl Schildkraut, and Dmitrii Zhelezov. The sum-product conjecture is false for real numbers. arXiv:2605.28781 (2026), 25 pp

    Pith/arXiv arXiv 2026

  4. [4]

    A lower bound on the trace norm of boolean matrices and its applications

    Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, and Morgan Shirley. A lower bound on the trace norm of boolean matrices and its applications. Algorithmica 88 (2026), \#54

    2026

  5. [5]

    Separation of the factorization norm and randomized communication complexity

    Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, and Morgan Shirley. Separation of the factorization norm and randomized communication complexity. Computational Complexity 34 (2025), \#17

    2025

  6. [6]

    ``Equality alone does not simulate randomness.'' In Proceedings of the 34th Computational Complexity Conference (2020), \#14

    Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals. ``Equality alone does not simulate randomness.'' In Proceedings of the 34th Computational Complexity Conference (2020), \#14

    2020

  7. [7]

    Sign-rank of k -Hamming distance is constant

    Mika G \"o \"o s, Nathaniel Harms, Valentin Imbach, and Dmitry Sokolov. Sign-rank of k -Hamming distance is constant. arXiv:2506.12022 (2025), 19 pp

    arXiv 2025

  8. [8]

    Equality is far weaker than constant-cost communication

    Mika G \"o \"o s, Nathan Harms, and Artur Riazanov. Equality is far weaker than constant-cost communication. arXiv:2507.11162 (2025), 15 pp

    arXiv 2025

  9. [9]

    Richter, and Anastasia Sofronova

    Mika G \"o \"o s, Nathaniel Harms, Florian K. Richter, and Anastasia Sofronova. No constant-cost protocol for point-line incidence. arXiv:2604.03805 (2026), 18 pp

    Pith/arXiv arXiv 2026

  10. [10]

    Dimension-free bounds and structural results in communication complexity

    Lianna Hambardzumyan, Hamed Hatami, and Pooya Hatami. Dimension-free bounds and structural results in communication complexity. Israel Journal of Mathematics 253 (2023), 555--616

    2023

  11. [11]

    ``Lower bound methods for sign-rank and their limitations.'' In Approximation, R andomization, and C ombinatorial O ptimization

    Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, and Rosie Zhao. ``Lower bound methods for sign-rank and their limitations.'' In Approximation, R andomization, and C ombinatorial O ptimization. A lgorithms and T echniques (2022), \#22

    2022

  12. [12]

    Randomized communication and implicit graph representations

    Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev. Randomized communication and implicit graph representations. TheoretiCS 4 (2025), \#20

    2025

  13. [13]

    Nathaniel Harms and Viktor Zamaraev. ``Randomized communication and implicit representations for matrices and graphs of small sign-rank.'' In Proceedings of the 2024 Annual ACM--SIAM Symposium on Discrete Algorithms (2024), 1810--1833

    2024

  14. [14]

    Lower bounds in communication complexity based on factorization norms

    Nati Linial and Adi Shraibman. Lower bounds in communication complexity based on factorization norms. Random Structures and Algorithms 34 (2009), 368--394

    2009

  15. [15]

    Daniel A. Marcus. Number Fields. (Heidelberg: Springer--Verlag, 1977)

    1977

  16. [16]

    Tours de corps de classes et estimations de discriminants

    Jacques Martinet. Tours de corps de classes et estimations de discriminants. Inventiones Mathematicae 44 (1978), 65--73

    1978

  17. [17]

    Probabilistic communication complexity

    Ramamohan Paturi and Janos Simon. Probabilistic communication complexity. Journal of Computer and System Sciences 33 (1986), 106--123

    1986

  18. [18]

    Sherstov and Andrey A

    Alexander A. Sherstov and Andrey A. Storozhenko. The communication complexity of approximating matrix rank. arXiv:2410.20094 (2024), 85 pp

    arXiv 2024

  19. [19]

    Endre Szemer\'edi and William T. Trotter. ``Extremal problems in discrete geometry.'' Combinatorica 3 (1986), 381--392

    1986