Questions tagged [communication-complexity]
The communication-complexity tag has no summary.
6 questions
0 votes
0 answers
42 views
relation between the approximate $\gamma_2$ norms of Boolean matrix and sign matrix
For a real matrix $A$, its $\gamma_2$-norm is defined as $$\gamma_2(A)=\min_{X,Y:A=XY}||X||_{row}||Y||_{col},$$ where $||\cdot||_{row},||\cdot||_{col}$ are defined as the maximum $\ell_2$-norm of row ...
- 521
0 votes
0 answers
128 views
Permutation of low circuit complexity
Let $\mathcal P$ be the set of permutations in $F_2^n$. I am interested in the circuit complexity of such functions in $AC^k[2]$ setup. What are the relevant upper and lower bounds in this context? ...
- 111
3 votes
0 answers
101 views
Quantum versus classical communication complexity
Problem. Is it true that any 2-party communication problem $f(x,y)$ of poly-logarithmic complexity in the quantum simultaneous message passing model ($Q''$) has complexity $n^{o(1)}$ (i.e., strongly ...
- 4,645
2 votes
1 answer
273 views
Entropy x Complexity - Shannon x Kolmogorov [closed]
This is a very common question but I think I’m posting it in a different way. Suppose that we have 256 different possible messages with uniform distribution to be represented in a binary code. Then ...
- 21
3 votes
0 answers
333 views
what is the largest gap between rank and approximate rank
$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} ...
- 363
13 votes
1 answer
648 views
Space Bounded Communication Complexity of Identity
$\bf Definition.$ We define the space bounded communication in the following way. A and B are supernatural beings capable of computing anything but they only have a limited amount of memory and that ...
- 19.7k