The communication-complexity tag has no wiki summary.
1
vote
0answers
30 views
mututal data authentication from a short authentication string
For all $n$, $\:$range($\hspace{.005 in}n$)$\:$ is the set of non-negative integers that are less than $n$.
What is known about how many rounds of communication are
needed for mutual data ...
7
votes
1answer
123 views
Why does the log-rank conjecture use rank over the reals?
In communication complexity, the log-rank conjecture states that
$$cc(M) = (\log rk(M))^{O(1)}$$
Where $cc(M)$ is the communication complexity of $M(x,y)$ and $rk(M)$ is the rank of $M$ (as a ...
3
votes
0answers
113 views
Streaming Algorithm Lower Bounds by Communication Complexity
I am learning the methods for proving lower bounds on streaming algorithms using communication complexity.
My question is about a basic technique to prove lower bounds on streaming models using the ...
0
votes
1answer
131 views
“Send Once”-One way Multiparty Communication Complexity
There are plenty results on multiparty communication complexity, and one way protocol which anyone playing communicatin games is able to send one person, is a basic setting.
I want to consider more ...
4
votes
1answer
92 views
Streaming Algorithms: Motivations for estimating frequency moments
The celebrated AMS paper "The space complexity of approximating the frequency moments" defines the problem as following:
Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in ...
11
votes
1answer
175 views
Best communication complexity lower bound of disjointness
It is well known that no deterministic two-party protocol can solve disjointness problem (DISJ) on $n$-bit inputs without sending n+1 bits in the worst case (see, e.g., the book by Kushilevitz and ...
7
votes
2answers
139 views
Delegating all of the work to the prover in $\mathcal{MA}$ protocols
An $\mathcal{MA}$ communication complexity protocol is communication complexity protocol that starts with an omniscient prover that sends a proof (that depends on the the specific input of the ...
6
votes
0answers
92 views
Communication complexity of random functions with limited independence
Let $X_0, \ldots, X_{2^n-1}$ be $k$-wise independent random $0/1$ variables over a sample space $\Omega$ and $Prob \left[ X_i = 1 \right] = p$ for every $i$ and some $0 < p < 1$. Let assume $n$ ...
8
votes
1answer
195 views
A balanced generalization of Hall’s theorem
Let $X$ and $Y$ be sets, and $\mathcal{B}$ be a partition of $X \times Y$. I would like to prove that there exists a distribution $\mathcal{D}$ over $X \times Y$ whose marginal is uniform over $X$, ...
3
votes
0answers
123 views
Lower Bound Methods in NonDet Communication Complexity
rank+($M$) is the minimum $r$ such that the following statement holds.
The statement : there exists matrices $U,V$ such that $M = UV$ and $U$ has $r$ columns and $V$ has $r$ rows.
Is rank+($M$) ...
5
votes
1answer
174 views
Average message complexity for the election problem on graphs
I am currently studying the election problem in distributed algorithms. There, I stumpled over one approach to implement a Chang-Roberts-like message extinction algorithm on graphs without requiring a ...
4
votes
0answers
157 views
Do the quantum communication complexity lower bounds hold when parties can send a “duplicated” qubits?
This question continues from the previous question where I mistakenly asked a question that is too general.
In quantum communication complexity, we always assume that Alice and Bob have unlimited ...
0
votes
2answers
245 views
Are Alice and Bob allowed to copy qubits in quantum communication complexity model?
In quantum communication complexity, we always assume that Alice and Bob have unlimited computational power and are still prove lower bounds such as the $\Omega(n)$ lower bounds of parity.
What ...
11
votes
0answers
305 views
Known upper bounds on the communication complexity of Karchmer-Wigderson games
In 1988 Karchmer and Wigderson established a nice characterization of the circuit
depth $d$ (DeMorgan circuits) of a Boolean function $f \colon \{0,1\}^n\rightarrow\{0,1\}$: $d$ is exactly the number ...
9
votes
3answers
198 views
Bounds on approximating frequency moments
Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in \{1,2,\dotsc,n\}$. For $i \in \{1,2,\dotsc,n\}$, let $m_i = |\{j : a_j = i\}|$. The $k$th frequency moment is defined to be
...
