New answers tagged communication-protocols
1
vote
Communication complexity of Dyck language
TL;DR: $n \le C(f) \le n+1$.
We can easily prove that $C(f) \ge n$. Consider the set of $x \in \{(,[\}^n$. There are $2^n$ such $x$-values. Each matches a different set of $y$-values. So, you need ...

D.W.♦
- 156k
Top 50 recent answers are included
Related Tags
communication-protocols × 100computer-networks × 48
protocols × 16
communication-complexity × 12
distributed-systems × 9
algorithms × 8
information-theory × 7
tcp × 6
complexity-theory × 4
reference-request × 4
performance × 4
consensus × 4
ip × 4
probability-theory × 3
error-correcting-codes × 3
network-analysis × 3
network-flow × 2
cryptography × 2
data-compression × 2
encoding-scheme × 2
storage × 2
upper-bound × 2
fault-tolerance × 2
blockchain × 2
graphs × 1