16
In a recent paper, Braverman, Garg, Pankratov, and Weinstein compute the value of $\delta$ to be exactly some constant around 0.4827, up to sublinear factors. This gives a tight bound on the communication complexity of disjointness.
The constant itself was found using a computer algebra system, and as far as I'm aware can't be expressed simply.
14
The conjecture fails over $\mathbb{F}_2$. Look at $M(x, y) = \langle x, y \rangle \bmod 2$, and $x, y \in \{0, 1\}^n$. The communication complexity is $\Omega(n)$, but the rank of $M$ over $\mathbb{F}_2$ is $n$, by the linearity of inner product.
14
There's been a fair bit of progress. On the specific problem of $F_k$, there is a matching upper and lower bound of $n^{1-2/k}$ for $k > 2$. The upper bounds come from this paper by Indyk and Woodruff (which appeared in STOC 2005) and the lower bounds are via the information complexity framework, due to Bar-Yossef et al and Chakrabarti et al.
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
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
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
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 ...
11
This is known as Greater-Than problem in communication complexity. An algorithm with $O(\log n) $ communication complexity exists (Exercise 3.18 in Nisan-Kushilevitz book).
Edit: The algorithm is due to Nisan (page 10): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdf
It uses the approach suggested by @Sasho ...
10
Let $D$ be the distribution on inputs that w.p. $p = 1/(1+\epsilon)$ picks $(x,x)$ for random $x$, and w.p. $1-p$ picks $(x,y)$ for random $x \neq y$. An appropriate choice of random coins leads to a deterministic protocol that never makes mistakes and outputs MAYBE w.p. at most $1/2$ with respect to $D$. In particular, it must answer YES on at least $1-(1/2)...
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
First I'll give some background and define approximate rank. A good reference is the recent survey by Lee and Schraibman Lower Bounds on Communication Complexity.
Definition: Let $A$ be a sign matrix. The approximate rank of $A$ with approximation factor $\alpha$, denoted $rank^\alpha(A)$, is
$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j] \leq \...
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
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/...
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
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'm sure you know the following paper, but I put a link to it because other readers may be interested: Interpolation by Games
This paper is an attempt to use the communication complexity framework to show lower bounds for cutting planes. The protocol is used to produce an interpolant circuit for unsatisfiable CNF:
$$
A(x,y)\lor B(x,z).
$$
Player $A$ ...
7
See The communication complexity of addition.
As Grigory mentioned, there is a protocol with communication $O(\log n)$. This is due to Nisan and Safra. Their protocol either uses public randomness or is not explicit. The above paper gives one that uses private randomness and is explicit (via a relatively standard use of pseudorandom generators); it also ...
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
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
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 ...
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
Let me add to Artem’s nice explanation a pedantic point about your wording “something a quantum algorithm cannot do.”
In the usual setting of communication complexity, each party is allowed to perform any local operations, regardless of whether it is computable or not. This is true in both classical and quantum cases. In this sense, each party is indeed ...
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
Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.
Only top voted, non community-wiki answers of a minimum length are eligible
