One of my favorite topics is communication complexity.  In this model, two parties, usually called Alice and Bob, want to answer a question, but neither one has sufficient information to do this on their own—only by sharing what they know can they answer it.  The question is how much information they need to exchange in order to do this.  For example, imagine that Alice and Bob want to arrange a meeting for next week, but both have busy schedules. How long can this conversation go on?

Alice: “Are you free Monday at 2pm?”

Bob: “No.  Monday 3pm good for you?”

Alice “No…”

It might be that the free slots in Alice’s schedule are completely disjoint from the free slots in Bob’s schedule and they can’t meet at all.  In fact this function, determining if Alice and Bob can meet, is known as disjointness and is the most important function in all of communication complexity.  And for this problem it turns out an optimal protocol is for Alice  right off the bat to send her whole schedule to Bob to check if they have a common free slot.

Mathematically, communication complexity is modeled by saying that Alice and Bob want to compute a function \(f(x,y)\) where Alice is given the input \(x\) and Bob the input \(y\), and the question is how much they have to communicate to do this for the worst-case input \(x,y\).  There are by now many variants of this model, for example where Alice and Bob can flip coins and only have to get the answer right with high probability, or can exchange quantum messages rather than classical strings.  Today at the CQT annual event we even heard about a model where the communication was via water and garden hoses!  Here we will stick to the plain old dry deterministic model.

The function \(f(x,y)\) is naturally viewed as a matrix  with rows labeled by the inputs to Alice, columns labeled by inputs to Bob, and the \((x,y)\) entry being \(f(x,y)\).  In the most common case, \(f(x,y)\) is a boolean function, so the matrix entries are just 0 or 1.  This matrix is known as the communication matrix, and analysis of matrix properties like rank play a large role in trying to figure out the communication complexity of a function.

For example, in the deterministic case it is known that the logarithm of the rank of the communication matrix is a lower bound on the communication complexity.  One of the biggest open problems in communication complexity, known as the log rank conjecture, is whether or not this bound is always close to the right answer—is the communication complexity always upper bounded by a polynomial in the logarithm of the rank of the communication matrix?  There has not been much progress on this question in the last 15 years, although just recently an interesting new approach has been suggested.

The log rank conjecture is known to be true…for a different kind of rank.  The usual rank of a matrix \(M\) is defined as the minimum \(k\) such that \(M\) can be written as a sum of \(k\) rank-one matrices \[M=\sum_{i=1}^k u_i v_i^t.\]

For a non-negative matrix, like the communication matrix of a boolean function, there is always such a decomposition where the \(u_i,v_i\) are non-negative vectors.  The non-negative rank of \(M\) is the minimum \(k\) such that \(M\) can be written as the sum of \(k\) non-negative rank-one matrices.  It turns out that the same proof that shows that the logarithm of the rank is a lower bound on communication complexity also shows that the logarithm of the non-negative rank is a lower bound on communication complexity.  This time, however, Lovasz proved that the logarithm of the non-negative rank of the communication matrix times the logarithm of the non-negative rank of the complement of the communication matrix is an upper bound on communication complexity.  (The complement of the communication matrix flips 0′s to 1′s and 1′s to 0′s.  These two matrices have essentially the same rank, but can have very different non-negative ranks.)

The problem with all this is that the non-negative rank is difficult to compute, both theoretically and practically.  Theoretically, unlike the rank which can be computed quickly, the non-negative rank is NP-hard to compute.  And in practice, we have depressingly few tools available to lower bound the non-negative rank.  A nice, simply stated open question is computing the non-negative rank of the \(n\)-by-\(n\) matrix whose \(i,j\) entry is \((i-j)^2\).  The regular rank of this matrix is 3, but it is conjectured that the non-negative rank is \(\Omega(n)\).