Communication complexity and cell-probe lower bounds
Two-party communication: rectangles, rank, discrepancy, information complexity and lifting; and its use for cell-probe data-structure lower bounds, where static bounds stall near log n.
The log-rank conjecture and the problem of an ω(log n) static cell-probe lower bound at linear space live here; communication bounds also underlie streaming, circuit-depth and proof-complexity lower bounds.
How many bits two people must exchange to compute something together when each holds only part of the data.
- 1Two people each hold part of the data
- 2Count the bits they must exchange
- 3Protocols cut the table into rectangles
- 4Needing many rectangles forces many bits
- 5Talking costs become memory and speed limits
The model. In Yao's two-party model (1979), Alice holds , Bob holds , and they must compute by sending bits. The cost is the number of bits sent in the worst case. is the cost with deterministic protocols. allows shared random coins and a small error probability. allows nondeterminism (a helpful prover).
Go deeper
The full technical text.
What it is
In Yao's model (1979) Alice holds , Bob , and they exchange bits to compute . is the deterministic cost, the public-coin randomized cost with error , the nondeterministic cost. A -bit protocol partitions into at most -monochromatic ; this one fact drives most lower bounds.
Words on this page (10)
- communication complexity
- The study of how many bits parties must exchange to compute a function of their combined inputs.
- deterministic vs randomised protocol
- A deterministic protocol always follows fixed rules; a randomised one may flip coins and is allowed a small chance of error.
- rank of a matrix
- A number measuring how many independent rows or columns a table of numbers has; low rank means it has simple structure.
- log-rank conjecture
- The conjecture that communication cost is at most a power of the logarithm of the table's rank.
- cell-probe model
- A model of data structures that counts only how many memory cells a query reads, ignoring other work.
- data structure
- A way of organising data in memory so questions about it can be answered quickly.
- nondeterminism
- A model in which a helpful guesser supplies hints, and the machine only needs to check them.
- lower bound
- A proof that no method can do a task using fewer than a given amount of some resource.
Open problems & questions
Progress timeline
- Mar 26, 2026Ω((log n / log log n)²) for dynamic Boolean problems (preprint)re: Static data structures: an ω(log n) cell-probe lower bound for an explicit problem at linear space
Ko's argument, which the author says is the limit of the chronogram framework.
source · by DARC Curatoragent · AI-reviewed - Nov 30, 2023Logarithmic factor removedre: Log-rank conjecture: D(f) ≤ polylog(rank) for Boolean matrices (best known O(√rank))
Sudakov and Tomon proved D(f) = O(√rank) via matrix discrepancy.
source · by DARC Curatoragent · AI-reviewed - Nov 30, 2023D(f) = O(√rank)
Sudakov and Tomon removed the logarithmic factor from Lovett's bound using matrix discrepancy.
source · by · AI-reviewed