Communication Complexity
E822918
Communication Complexity is a subfield of theoretical computer science that studies how much communication is required between parties to jointly compute a function of their distributed inputs.
Statements (66)
| Predicate | Object |
|---|---|
| instanceOf |
area of computational complexity theory
ⓘ
subfield of theoretical computer science ⓘ |
| analyzes | number of bits exchanged between parties ⓘ |
| appliesTo |
VLSI complexity
ⓘ
communication networks ⓘ data stream algorithms ⓘ distributed algorithms ⓘ parallel computing ⓘ |
| focusesOn | joint computation of a function of distributed inputs ⓘ |
| hasCanonicalText | Communication Complexity by Eyal Kushilevitz and Noam Nisan NERFINISHED ⓘ |
| hasKeyProblem |
disjointness lower bounds
ⓘ
equality problem ⓘ gap Hamming distance problem ⓘ greater-than problem ⓘ indexing problem ⓘ inner product problem ⓘ pointer chasing problem ⓘ set disjointness problem ⓘ |
| hasKeyResult |
Karchmer–Wigderson games
NERFINISHED
ⓘ
direct product theorems ⓘ direct sum theorems ⓘ log-rank conjecture NERFINISHED ⓘ lower bounds for disjointness ⓘ round elimination lemmas ⓘ |
| hasKeyTool |
corruption bound
ⓘ
discrepancy method ⓘ factorization norms ⓘ fooling set method ⓘ information-theoretic methods ⓘ partition bound ⓘ rank method ⓘ rectangle bounds ⓘ |
| hasResearcher |
Andrew Yao
NERFINISHED
ⓘ
Avi Wigderson NERFINISHED ⓘ Eyal Kushilevitz NERFINISHED ⓘ László Lovász NERFINISHED ⓘ Noam Nisan NERFINISHED ⓘ Ran Raz NERFINISHED ⓘ |
| includesModel |
multi-party communication model
ⓘ
number-in-hand model ⓘ number-on-forehead model ⓘ |
| provides |
lower bounds for circuit complexity
ⓘ
lower bounds for data structures ⓘ lower bounds for distributed computing ⓘ lower bounds for property testing ⓘ lower bounds for streaming algorithms ⓘ |
| relatedTo |
circuit complexity
ⓘ
coding theory ⓘ game theory ⓘ information theory ⓘ proof complexity ⓘ pseudorandomness ⓘ |
| studies |
amount of communication required to compute functions
ⓘ
communication required between distributed parties ⓘ |
| typicallyInvolves | two-party communication model ⓘ |
| usesConcept |
communication protocol
ⓘ
deterministic communication complexity ⓘ distributional complexity ⓘ information complexity ⓘ interactive communication protocols ⓘ nondeterministic communication complexity ⓘ one-way communication protocols ⓘ private-coin protocols ⓘ public-coin protocols ⓘ quantum communication complexity ⓘ randomized communication complexity ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.