Research problems in communication complexity

Question

There have been many open challenges questions in this forum.

For instance,

• Research and open challenges in Programming Language Theory
• What are current open problems in compiler theory?
• Outstanding conjectures and open problems in (algorithmic) game theory?
• Open problems on the frontiers of TCS
• Open problems related to Graph isomorphism

What are some of research avenues, areas available within communication complexity? What are some of most interesting open problems?

Some famous open problems AFAIK are status of log-rank conjecture, status of $\mathsf{IP}^{}\notin\mathsf{PH}^{cc}$, status of examples of natural problems in $\mathsf{NP}_k^{cc}$,$\mathsf{coNP}_k^{cc}$.

What are some of lesser known open problems or areas that are not yet mature within communication complexity or areas that have made new progress but much more needs to be done?

Are there any problems relating other areas such as circuit complexity, machine learning etc?

AFAIK communication complexity is more about finding bounds that about algorithms. Are there any problems with number theoretic, algebraic, geometric flavor or more generally in an algorithmic flavor?

More generally what would be some areas a newly entered person should focus energy to select a problem to work on (comm complexity field does not have many hearsay research topics as other traditional areas in mainstream theory CS with direct real world applications)?

Answer 1

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 bounds (such as for Disjointness or Equality) and apply these to get new lower bounds in other areas of computer science. New applications of communication complexity pop up all the time, and if you can find a niche no one's considered before, you might be able to leverage the existing bounds you're learning now rather than having to develop new lower bounds. This will help you get some papers out while you're learning all about communication complexity ;)

Another suggestion is to work hard to ask new questions people haven't yet considered, or to think about new settings that are fresh and less well-studied. Multiparty communication might be a good area to look at---it is generally less understood than two-party communication, and (IMO at least) there's lots of fresh motivation for studying it (from e.g. multicore processors to wireless sensor networks)

For a concrete open problem, there's a nice one from multiparty communication in the number-on-the-forehead (NOF) model. In the NOF communication model, there are $k$ players who wish to compute some function $f(x_1,\ldots, x_k)$ on $k$ inputs. However, each player $PLR_i$ sees every input except $x_i$. (You can imagine $PLR_i$ having $x_i$ written on his forehead.) Because lots of input is shared between players, it should be easier to compute functions of their input. Conversely, proving lower bounds on the communication complexity in the NOF model is harder.

Here's a $\textbf{big open problem}$ in this area: come up with some explicit function f(x_1,\ldots, x_k) for k=polylog(n) such that $\omega(polylog(n))$ communication is required in the NOF model.

Through a chain of results from the early nineties [Hastad-Goldman91, Beigel-Tarui94], it's known that such a result would imply that $f \not\in ACC_0$. For this connection to circuit complexity, you're actually free to assume that each player sends a single message to some "referee" who compiles the messages to produce an output. Lower bounds even in this restricted setting are far from what we'd like. The current state-of-the-art lower bound techniques for the NOF model don't give lower bounds better than $\Omega(n/2^k)$ or thereabouts. These become trivial once $k > \log(n)$.

Answer 2

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:

1. (KN 2.10) Is it true that $D(f) \le O(\log \chi(f))$? Here $\chi(f)$ is the minimal number of $f$-monochromatic rectangles into which the input space $X \times Y$ can be partitioned. $D(f) \ge \log \chi(f)$ was shown by Yao in 1979, and $D(f) \le O((\log \chi(f))^2)$ was shown by Aho/Ullman/Yannakakis in 1983. See also KN Theorem 2.11 and the historical discussion in the bibliographic notes to Chapter 2.
2. (Log-rank conjecture, KN 2.20) Is it true that $\log\chi(f) \le (\log rk(M_f))^{O(1)}$ for every Boolean function $f$? Here $M_f$ is the communication matrix of $f$, and $rk(M)$ denotes the rank of matrix $M$.
3. Is it true that $R(f) \le poly(Q(f))$? Here $R(f)$ denotes the bounded-error communication complexity of $f$ and $Q(f)$ the quantum communication complexity. Note that $Q(f) \le R(f)$ by definition.
4. Prove that $D(IP^k_n) \ge n^\epsilon$ for, say, $k = \lceil (\log n)^2\rceil$ and some fixed constant $\epsilon > 0$. Here $IP^k_n$ denotes the inner product function with respect to $k$-party NOF protocols.

As is hinted at by Razborov's survey, there are open questions about the quantum communication setting; this area is not covered by the 1997 textbook.

Edit 2015-03-14: After some thought, I don't understand problem 4, since the telescope protocol of Grolmusz uses $2k-1$ bits of communication to compute $IP^k_n$ per block of at most $2^{k-1}-1$ rows in the communication matrix. For $k \ge 2+\log n$, there is precisely one such block and the cost of the protocol is then just $2k-1$ bits. In particular, for $k=(\log n)^2$ this is $2(\log n)^2 - 1 = o(n^\epsilon)$ bits for every $\epsilon > 0$. In summary, IP seems to have structure that can be exploited in the number-on-forehead setting when there are a large number of parties. To reach the $\Omega(n)$ lower bound in the region $2+\log n \le k \le n/2$ therefore seems to require a different function.