Introduction to Communication Complexity
Communication complexity measures the amount of information that must be exchanged between two or more parties to solve a computational problem. Introduced by Andrew Yao in 1979, it provides a mathematical framework for analyzing distributed algorithms, data structures, streaming algorithms, and circuit complexity. Understanding communication complexity helps optimize algorithms where data transfer between processors, memory hierarchies, or networked systems is a bottleneck.
Core Concepts and Definitions
Basic Communication Model
| Concept | Definition |
|---|---|
| Two-Party Model | Alice has input x, Bob has input y; they communicate to compute f(x,y) |
| Communication Protocol | Specification of messages exchanged to compute the function |
| Communication Complexity | Minimum number of bits that must be exchanged in worst case |
| Deterministic Complexity | D(f): Minimum bits needed in any deterministic protocol |
| Randomized Complexity | R(f): Minimum expected bits needed with random coin flips |
| Public vs. Private Coins | Whether random bits are shared (public) or separate (private) |
Communication Matrix
For a function f(x,y), the communication matrix Mf has rows indexed by x, columns indexed by y, and Mf[x,y] = f(x,y).
Properties:
- Monochromatic Rectangle: Submatrix where all entries have the same f(x,y) value
- Protocol Partition: Any protocol partitions the matrix into monochromatic rectangles
- Rectangle Complexity: Log₂ of minimum number of monochromatic rectangles needed
Key Communication Models
Deterministic Communication
- Definition: Parties follow fixed protocol without randomization
- Complexity Measure: D(f) = worst-case bits exchanged
- Lower Bound Technique: Log of minimum number of monochromatic rectangles
Randomized Communication
| Model | Definition | Error | Complexity |
|---|---|---|---|
| Las Vegas | Always correct, randomized running time | None | R₀(f) |
| Monte Carlo (One-sided) | May err on one type of input | ε one-sided | R¹ₑ(f) |
| Monte Carlo (Two-sided) | May err on any input with bound | ε | Rₑ(f) |
| Public Coin | Random bits visible to all parties | ε | R^pub_ε(f) |
| Private Coin | Each party has own random bits | ε | R^priv_ε(f) |
Multi-Party Models
- Number-in-Hand: Each party has its own input
- Number-on-Forehead: Each party sees everyone’s input except their own
- Coordinator Model: Parties communicate through central coordinator
- Blackboard/Broadcast: Messages sent to all parties simultaneously
Complexity Bounds and Relationships
Fundamental Inequalities
- D(f) ≥ R₀(f) ≥ Rₑ(f)
- R^pub_ε(f) ≤ R^priv_ε(f) ≤ R^pub_ε(f) + O(log n)
- R^pub_ε(f) ≥ Ω(log rank(Mf))
- D(f) ≥ log₂ χ(Mf) where χ is chromatic number of matrix
Complexity Classes
| Class | Definition |
|---|---|
| P^cc | Problems with polylog communication complexity |
| BPP^cc | Problems with bounded-error randomized protocols |
| NP^cc | Problems where Alice can convince Bob with proof |
| co-NP^cc | Complement of NP^cc |
| Σₖ^cc, Πₖ^cc | Communication complexity polynomial hierarchy |
Key Lower Bound Techniques
Rectangle-Based Methods
| Technique | Description | When to Use |
|---|---|---|
| Fooling Set | Set of input pairs that must be in different rectangles | Simple deterministic lower bounds |
| Rank Lower Bound | D(f) ≥ log₂ rank(Mf) | Matrix-based analysis |
| Discrepancy | Measures rectangle uniformity for function values | Randomized protocols |
| Corruption | How well large rectangles can approximate f | Strong randomized bounds |
| Rectangle Corruption | Fraction of inputs in rectangle where protocol errs | Two-sided error protocols |
Information Theory Methods
| Technique | Description | Formula |
|---|---|---|
| Information Cost | Expected information revealed about inputs | IC(π) = I(X;Π|Y) + I(Y;Π|X) |
| External Information | Information revealed to observer | IC^ext(π) = I(XY;Π) |
| Information Complexity | Minimum information cost for any protocol | IC(f) = inf_π{IC(π)} |
Complexity Measures Relationships
- Communication Complexity ≥ Information Complexity
- Public-coin protocols can simulate private-coin with logarithmic overhead
- Information complexity is additive for function composition
Standard Communication Problems and Bounds
| Problem | Description | Complexity | Notes |
|---|---|---|---|
| Equality (EQ) | Determine if x = y | D(EQ) = n, R(EQ) = O(log n) | Huge gap between deterministic and randomized |
| Disjointness (DISJ) | Determine if x and y share a 1 | D(DISJ) = Θ(n), R(DISJ) = Θ(n) | Hard even for randomized |
| Greater-Than (GT) | Is x > y? | D(GT) = R(GT) = Θ(log n) | Binary search is optimal |
| Index | Bob has i, Alice has x_1,…,x_n; compute x_i | D(INDEX) = Θ(n) | One-way communication |
| Set Intersection | Output A ∩ B | Θ(n) | Cannot do better than sending sets |
| Hamming Distance | Count positions where x and y differ | Θ(n) | Randomization doesn’t help much |
| Gap Hamming | Is Hamming distance >n/2+√n or <n/2-√n? | Θ(n) | Important in streaming algorithms |
Notable Lower Bounds
| Problem | Deterministic | Randomized | Notes |
|---|---|---|---|
| Equality | n | Θ(log n) | Fingerprinting gives exponential speedup |
| Disjointness | n | Θ(n) | Fundamental lower bound in many applications |
| Inner Product | n | Θ(n) | Hard even with randomization |
| Majority | n | Θ(n) | Computing majority of coordinate-wise AND |
| k-th Element | Θ(n) | Θ(n) | Selection problem |
Multi-Round vs. One-Way Communication
Round Complexity
| Rounds | Impact | Examples |
|---|---|---|
| One-way | Alice sends message, Bob computes | INDEX requires Θ(n) bits |
| Two-way, const rounds | Limited back-and-forth | Some problems have exponential gap |
| Logarithmic rounds | Binary search-style protocols | Often sufficient for many problems |
| Unbounded rounds | Maximum power | Required for some problems |
Round Reduction Techniques
- Round Elimination: Remove first round with small information cost
- Message Compression: Reduce message size while preserving information
- Direct Sum: Analyze communication required for solving multiple instances
Applications of Communication Complexity
Data Structures
| Application | Relationship | Example |
|---|---|---|
| Static Data Structures | Space×Time ≥ Communication Complexity | Cell probe model lower bounds |
| Dynamic Data Structures | Update/Query time ≥ Communication Cost | Partial sums, range queries |
| Succinct Data Structures | Space bounds related to communication | Bit vectors, rank/select |
Streaming Algorithms
| Application | Relationship | Example |
|---|---|---|
| Space Lower Bounds | Stream space ≥ Communication | Frequency moments require Ω(√n) space |
| Multiple Passes | Pass×Space trade-offs | Graph connectivity in O(log n) passes |
| Sketching | Sketch size ≥ Communication | L₀, L₁, L₂ norm estimation |
Circuit Complexity
- Karchmer-Wigderson Games: Relate depth to communication
- Formula Size Lower Bounds: Based on communication complexity
- Monotone Circuits: Strong lower bounds via communication arguments
Distributed Computing
| Application | Relationship | Example |
|---|---|---|
| Message Complexity | Total bits exchanged | Graph connectivity requires Ω(n log n) |
| Round Complexity | Number of synchronous rounds | MST requires Ω(D) rounds (D = diameter) |
| Congestion | Maximum bits per channel | Routing requires Ω(congestion) rounds |
Information Complexity Framework
Properties
- Chain Rule: IC(f,g) = IC(f) + IC(g|f)
- Data Processing Inequality: Processing cannot increase information
- Additivity: IC(f^n) = n·IC(f) for n independent copies
- Direct Sum: Solving n copies costs n times one copy
Key Results
- Information = Amortized Communication: IC(f) = lim_n→∞ CC(f^n)/n
- Compression: Protocols with information I can be compressed to Õ(I) bits
- Interactive Compression: Bounded-round compression with overhead proportional to rounds
Common Challenges and Solutions
| Challenge | Solution Approach | Complexity Impact |
|---|---|---|
| Large Input Domains | Hashing/fingerprinting | Reduces complexity logarithmically |
| Finding Lower Bounds | Rectangle-based methods | Proves optimality of protocols |
| Multiple Parties | Coordinator model reduction | Simplifies analysis |
| Function Composition | Direct sum arguments | Establishes complexity bounds |
| Long Protocols | Protocol compression | Reduces message sizes |
Quantum Communication Complexity
| Model | Advantage | Limitations |
|---|---|---|
| Quantum Messages | Exponential advantage possible | Limited to specific problems |
| Entanglement | Can reduce communication | Not always helpful |
| Quantum Lower Bounds | Often match classical for many functions | Require different proof techniques |
Notable Quantum Results
- Equality: O(√log n) quantum bits vs. O(log n) classical bits
- Disjointness: Ω(√n) quantum bits (quadratic speedup over classical)
- Hidden Matching: Exponential separation between quantum and classical
Technical Tools and Mathematical Background
Essential Mathematical Concepts
- Linear Algebra: Matrix rank, eigenvalues, spectral analysis
- Information Theory: Entropy, mutual information, KL-divergence
- Probability Theory: Concentration bounds, Chernoff bounds
- Combinatorics: Rectangle partitioning, coloring
Key Inequalities
- Entropy Bounds: H(X) ≤ log |X|
- Mutual Information: I(X;Y) = H(X) – H(X|Y) = H(Y) – H(Y|X)
- Fano’s Inequality: To transmit n bits with error ε requires ≈ n bits
- Data Processing: If X → Y → Z, then I(X;Z) ≤ I(X;Y)
Recent Advances and Open Problems
Breakthrough Results
- Information = Communication: Braverman’s result on information complexity
- Number-on-Forehead: Improved lower bounds for k ≥ 3 parties
- Space-Round Tradeoffs: Near-optimal bounds for streaming models
- XOR Functions: Characterization based on Fourier coefficients
Major Open Problems
- Log-Rank Conjecture: Is D(f) ≤ poly(log rank(Mf))?
- Direct Sum: Is computing k copies k times harder than one copy?
- Disjointness: Optimal bound in number-on-forehead model?
- Round Complexity: Optimal trade-offs between rounds and communication
Best Practices for Communication Analysis
Protocol Design Principles
- Use Randomization: Often gives exponential improvements
- Balance Communication: Distribute bits evenly when possible
- Precomputation: Compute and share information beforehand if repeated
- Leverage Asymmetry: Assign more work to party with more data/resources
- Error Correction: Include redundancy for noisy channels
Analysis Methodology
- Start Simple: Begin with basic protocols before optimization
- Lower Bounds First: Establish fundamental limits
- Identify Bottlenecks: Focus optimization on communication-heavy components
- Decompose Problems: Break into simpler subproblems with known complexity
- Consider Amortized Costs: Analyze average cost over multiple operations
Resources for Further Learning
Foundational Books and Surveys
- “Communication Complexity” by Kushilevitz & Nisan
- “Lecture Notes on Communication Complexity” by Rao & Yehudayoff
- “Communication Complexity: A Modern Approach” by Braverman
Online Resources
- Scott Aaronson’s Complexity Zoo
- Communication Complexity Zoo (CC-Zoo)
- Theory of Computing Library (ToC)
Important Research Papers
- Yao’s 1979 seminal paper “Some Complexity Questions Related to Distributive Computing”
- Razborov’s 1992 “On the Distributional Complexity of Disjointness”
- Braverman’s 2012 “Interactive Information Complexity”