No Constant-Cost Protocol for Point--Line Incidence
This resolves an open conjecture and establishes a fundamental new separation in communication complexity for problems with constant support-rank.
The paper proves that the randomised communication complexity of the Point-Line Incidence problem is Θ(log n), confirming a conjecture that it is super-constant and providing the first example of a communication problem with constant support-rank but super-constant randomised complexity.
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 $Î(\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.