Randomized communication complexity of Point-Line Incidence is Theta(log n), the first constant support-rank example with super-constant complexity.
Equality alone does not simulate randomness
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
citation-role summary
background 2
citation-polarity summary
fields
cs.CC 2years
2026 2verdicts
UNVERDICTED 2roles
background 2polarities
background 2representative citing papers
Exponential lower bounds for cutting planes and Res(⊕) on binary clique formulas for random dense graphs, with polynomial randomized communication complexity for falsified clause finding.
citing papers explorer
-
No Constant-Cost Protocol for Point--Line Incidence
Randomized communication complexity of Point-Line Incidence is Theta(log n), the first constant support-rank example with super-constant complexity.
-
Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
Exponential lower bounds for cutting planes and Res(⊕) on binary clique formulas for random dense graphs, with polynomial randomized communication complexity for falsified clause finding.