New answers tagged communication-complexity
1
vote
Communication complexity of equality on graphs
Communication with partial information is the topic of Chapter 4.7 in the Kushilevitz-Nisan book, building mainly on work by Orlitsky. There they are concerned with the number of rounds in a ...
- 13.8k
Top 50 recent answers are included
Related Tags
communication-complexity × 138cc.complexity-theory × 35
lower-bounds × 24
reference-request × 19
it.information-theory × 9
co.combinatorics × 8
big-picture × 6
quantum-computing × 5
circuit-complexity × 5
linear-algebra × 5
boolean-functions × 5
quantum-information × 5
open-problem × 5
query-complexity × 5
streaming × 4
ds.algorithms × 3
randomized-algorithms × 3
matrices × 3
survey × 3
data-streams × 3
zero-knowledge × 3
norms × 3
complexity-classes × 2
lo.logic × 2
fl.formal-languages × 2