No Constant-Cost Protocol for Point--Line Incidence
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910103099146240 |
|---|---|
| author | Göös, Mika Harms, Nathaniel Richter, Florian K. Sofronova, Anastasia |
| author_facet | Göös, Mika Harms, Nathaniel Richter, Florian K. Sofronova, Anastasia |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_03805 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | No Constant-Cost Protocol for Point--Line Incidence Göös, Mika Harms, Nathaniel Richter, Florian K. Sofronova, Anastasia Computational Complexity 68Q11, 68Q25, 11B30 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. |
| title | No Constant-Cost Protocol for Point--Line Incidence |
| topic | Computational Complexity 68Q11, 68Q25, 11B30 |
| url | https://arxiv.org/abs/2604.03805 |