{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreia4ctphb6buztovawggalk67bujotqbahfo3jjzygl736sk5h4ote",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mixatwn4yk42"
  },
  "path": "/report/2026/049",
  "publishedAt": "2026-04-07T11:19:20.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "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.",
  "title": "TR26-049 |  No Constant-Cost Protocol for Point–Line Incidence | \n\n\tMika Göös, \n\n\tNathaniel Harms, \n\n\tFlorian Richter, \n\n\tAnastasia Sofronova"
}