Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-049 | 7th April 2026 13:25

No Constant-Cost Protocol for Point–Line Incidence

RSS-Feed




TR26-049
Authors: Mika Göös, Nathaniel Harms, Florian Richter, Anastasia Sofronova
Publication: 7th April 2026 14:19
Downloads: 78
Keywords: 


Abstract:

Alice and Bob are given $n$-bit integer pairs $(x,y)$ and $(a,b)$, respectively, and they must decide if $y=ax+b$. We prove that the randomised communication complexity of this Point–Line Incidence problem is $\Theta(\log n)$. This confirms a conjecture of Cheung, Hatami, Hosseini, and Shirley (CCC 2023) that the complexity is super-constant, and gives the first example of a communication problem with constant support-rank but super-constant randomised complexity.



ISSN 1433-8092 | Imprint