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