13
Indeed, for distjointness of sets of size $\log(n)$ out of $n$ items, it is known that
the $0$-error randomized communication complexity is $\Theta(\log n)$, while the deterministic
complexity is $\Theta(\log^2 n)$.
Recall that there can be at most a quadratic gap since the $0$-error randomized complexity is bounded from below by the non-deterministic ...
12
Books:
Eyal Kushilevitz and Noam Nisan, "Communication Complexity", 2006.
Stasys Jukna, "Boolean Function Complexity: Advances and Frontiers", 2012. (Part II of the book is dedicated to Communication Complexity.)
Articles:
Alexander Razborov, "Communication Complexity".
Lecture Notes:
Toni Pitassi, "Communication Complexity, Information Complexity and ...
12
Recent work by Alon, Moran, and Yehudayoff gives an $O(n/\log n)$ approximation algorithm. Let $d$ be the VC-dimension of a sign matrix $S$. The idea is that
there exists an efficiently computable matrix $M$ with sign pattern $S$ such that $\mathrm{rank}\ M = O(n^{1-1/d})$;
the sign rank of $S$ is at least $d$.
So the algorithm computes $M$ and outputs ...
12
The bounds...
We have in fact $NFA(L) \ge Cov(M) + Cov(N)$, see Theorem 4 in (Gruber & Holzer 2006). For an upper bound, we have $2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$, see Theorem 11 in the same paper.
...cannot be substantially improved
There can be a subexponential gap between $Cov(M)+Cov(N)$ and $NFA(L)$. The following example, and the proof ...
10
I'll start with answers to your general questions, then give one nice open problem with applications towards circuit complexity.
It's hard to say what areas a new communication complexity researcher should delve into, since easy problems have likely been solved already, and harder problems are hard ;) One suggestion is to take known communication lower ...
9
This question has just been resolved! As I mentioned, it was known that
$Pn(f) \leq D(f) \leq (Pn(f))^2$,
but it was a major open problem to show that either $Pn(f) = \Theta(D(f))$ or that there exists a function for which $Pn(f) = o(D(f))$.
A few days ago this was resolved by Mika Göös, Toniann Pitassi, Thomas Watson (http://eccc.hpi-web.de/report/...
9
$N^1(DISJ_n) \geq n$.
The fooling set technique actually provides lower bounds on the cover number. $C^1(f)$ is the minimum number of monochromatic rectangles needed to cover the $1$-inputs of $f$. In the fooling set technique, you create a set of input pairs and show that each must lie in distinct monochromatic rectangles.
In this case, look at the set ...
9
Here is a simple protocol for Hamming distance that uses $O(\varepsilon^{-2} \log n)$ bits. The protocol is essentially the Alon, Matias, Szegedy second moment sketch. Or you can think of it as a version of the Johnson-Lindenstrauss lemma.
I am assuming that Alice has a vector $x \in \{0,1\}^n$ and Bob has a vector $y \in \{0,1\}^n$, and they share ...
8
There are examples of $n\times n$ real matrices of rank at most $3$ and non-negative rank at least $\sqrt{2n}$. So the non-negative rank cannot be bounded by any function of the rank in general. The construction I am aware of goes through extension complexity. An explanation follows.
The extension complexity $xc(K)$ of a convex set $K$ in $\mathbb{R}^d$ is ...
8
This is equivalent to the biclique partition number of a bipartite graph. You can think of M as representing a bipartite graph $G$ on $[n] \times [m]$ in the natural way: $M_{i,j}$ is 1 if and only if there is an edge $(i,j)$ in G (where $i$ is an element of the left partition, and $j$ an element of the right partition). Then $M$ has binary rank $r$ if and ...
8
There seem to be typos in what you wrote; I take it you're asking: is there a function $f \in NEXP$ such that for all polynomials $p$ and infinitely many $n$, no ACC0 circuit of $p(n)$ size can compute $f_n$ on more than $1-1/p(n)$ inputs of length $n$?
As far as I know, this is open. But here is a possible path to doing it. We know that every $NEXP$-...
8
A quadratic separation between $\log\chi_0$ and $\log\chi_1$ is proved in a paper by Göös, Jayram, Pitassi and Watson, see the ECCC report.
In Theorem 2 they construct a function $F$ with small $\log\chi_1(F)$, and they say "In fact, we prove Theorem 2 by showing that (the negation of) the function $F$ has high approximate nonnegative rank". Observe that $\...
7
After more than two years, I have to assume the answer is "no". (Posting this stub answer so the question can be marked as answered.)
7
You remark that lower bounds on $Pn(f)$ are closely related to all existing lower bound techniques. For Boolean functions this seems to be true, as long as the log-rank conjecture is true.
However, $Pn(f)$ can be exponentially larger than the fooling set bound.
It is not clear to me how much $Pn(f)$ and $D(f)$ can differ in the non-Boolean case.
In the ...
7
The fundamental reason there are such limitations on communication complexity is that there is only ever a linear amount of total information that needs to be communicated (the inputs). Although Hartmut Klauck already essentially pointed this out in his answer, I wanted to highlight an answer to the other OQ regarding the underlying reason for this ...
7
I think this can be done with $\log n \cdot\log t + t \cdot\log\log t$ bits of nondeterministic communication.
By encoding all strings with an error correcting code, we may assume that whenever we have an input pair $(x,y)$ with $x\neq y$ the two strings differ in a constant fraction of coordinates. Suppose we are given $t$ pairs $(x^j,y^j)_{j\in[t]}$ that ...
7
For the lower bound, consider the following problem: Alice is given $x \in \{0,1\}^n$ and Bob is given $i \in [n]$. Their goal is to output $x_i$ (in other words, they need to decide if $i$ is in the set indicated by $x$). This problem is called $INDEX$ in the literature. For the rest of this answer, I assume that Alice always speaks first.
Claim: the ...
7
What you call $cc_{max}$ is known as the worst-case partition communication complexity, and what you call $cc_{min}$ is known as the best-case partition communication complexity.
These have been studied for several functions, you can find some results in the book of Kushilevitz and Nisan in chapter 7.
I'm not aware of anyone introducing the difference or the ...
7
If you look at the MNSW proof carefully, the base case can be taken to be the trivial fact that a $0$-round protocol for $\textrm{GT}_n$ with $n = 1$ requires one bit of communication.
If the goal is simply to convince oneself from first principles that $\textrm{R}^\to(\textrm{GT}_n) = \Omega(n)$, this is immediate by reduction from the AUGMENTED-INDEX ...
6
I don't know of any function with communication much higher than the $\gamma_2$ bound. However, my intuition of why it is not tight is because the $\gamma_2$-norm is also a lower bound for QCMA communication. See this paper by Klauck for the definition of QCMA communication.
To prove the lower bound on QCMA communication using the $\gamma_2$-norm you can ...
6
Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.
6
Several long-standing key open problems are in the Kushilevitz and Nisan textbook (see also the list of errata which mentions that Open Problem 8.6 was solved by Dietzfelbinger).
Razborov's 2011 introductory survey lists four open problems, two of which are also in the KN textbook:
(KN 2.10) Is it true that $D(f) \le O(\log \chi(f))$?
Here $\chi(f)$ is the ...
6
Let $C:\{0,1\}^{n} \to \{0,1\}^{2n}$ be an error correcting code with linear distance. Let $g: \{0,1\}^{n} \times \{0,1\}^{n} \to \{0,1\}$ be a function whose randomized communication complexity is large (say, $\Omega(\sqrt{n})$ or $\Omega(n))$.
Define $f: \{0,1\}^{2n} \times \{0,1\}^{2n} \to \{0,1,*\}$ to be the partial function that on codewords of $C$ ...
5
I think I can suggest the problem, which is not widely known, but for which I'm interested in. Suppose we have $n$ permutations $\pi_i$ in $S_3$. Alice, Bob and Carol receive first, second and third elements of all permutations, respectively. The goal is to compute $\prod_i sgn(\pi_i)$, where $sgn(\pi_i)$ is a sign of permutation $\pi_i$ (can take -1 or +1). ...
5
Yes, information theory is useful for proving lower bounds on the query complexity of problems in Computer Science.
Alexander Golynski gave a good example in his ground breaking paper titled "Cell probe lower bounds for succinct data structures", presented at SODA 2009. He uses information theory to prove a lower bound on query complexity, which in turns ...
5
It seems to me that there is some incoherency in the question. What do you mean by better?
Are you looking for a function where $N(f) \ll D(f)$ or a function where $D(f) \ll N(f)$?
Deterministic protocols are a special case of nondeterministic protocols, so we always have $N(f) \leq D(f)$.
For examples of functions where $N(f) \ll D(f)$ have a look at the ...
5
(Reduction from set disjointness)
Suppose Alice and Bob are given sets $S, T \subseteq [n]$ with the guarantee
that $|S\cap T| \leq 1$. Alice and Bob run the protocol for finding the common
element of $S$ and $T$ assuming that their sets have a non-trivial intersection
to decide a common element $X$. Now, they can communicate with each other to
verify that $...
5
The lower bound problem you're looking for is the GAP-HAMMING problem. Sherstov has a "simplest" result for the general communication complexity of GAP HAMMING, and in his paper he has a nice review of the related literature, including the sequence of references for the linear lower bound on the one-way communication complexity of GAP HAMMING.
5
I will give two upper bounds. Let $A$ and $B$ be the sets given to Alice and Bob, respectively, and put $a=|A|$, $b=|B|$, $c=|A\cap B|$.
First, there is a randomized protocol that, given $d>0$ and $\epsilon>0$, computes with probability $\ge1-\epsilon$ an approximation of $c$ up to additive error $d$, using $O\Bigl(\left(\frac{\min\{a,b\}}d\right)^2\...
4
The "number in hand" model is the one I was thinking of, and there is quite a bit of literature about it. In particular I found this paper of Jeff Phillips, Elad Verbin, and Qin Zhang from SODA 2012 [1]. In particular they prove lower bounds on the problem I was interested in using, the undirected graph connectivity problem, of $\Omega(nk / \log^2(k))$. Here ...
Only top voted, non community-wiki answers of a minimum length are eligible