Communication complexity lower bounds

I just discovered a spectacular survey article on communication complexity lower bounds. The paper is below.

Troy Lee and Adi Shraibman (2007) “Lower Bounds in Communication Complexity”,

Foundations and Trends® in Theoretical Computer Science: Vol. 3: No. 4, pp 263–399.

You can find a draft in Troy Lee's homepage.

Finished reading it, not with full details, but enough for understanding the bigger picture in the proof technique they use. Now I'm ready to read it for a second time, but this time going deeper into the details. First let's review the communication model. There are two players, Alice (A) and Bob (B), and they want to solve a problem together call it f which will be a boolean function. The input to f is divided between A and B, so in order to solve the problem they will need to communicate. The complexity is the minimum number of bits that need to be interchanged to solve the problem. The running time of A and B is not taken into account. All communication is defined by the communication matrix M, which is defined as M[x,y]=f(x,y), i.e. the rows and columns are indexed by the inputs to A and B, and each entry is the value of f. Changing the acceptance condition for the model we get a deterministic, randomized (two, one and zero-sided) or a nondeterministic model. If we allow the player to send qubits we get quantum. It can also be generalized to multiparty communication with all different flavors like the topology of communication, the way the parties access the input, etc.

Since communication complexity is more about lower bounds, all research is devoted to this. Upper bounds in this models are implied by upper bounds in the decision tree model. The general idea of proving lower bound is the following three steps procedure:

1. Embed the communication matrix onto the reals. This is done by a mapping from some operator norm to an euclidean norm.
2. Formulate the problem using the embedding as a maximization problem.
3. Give a witness for the objective function of the resulting program.

I would say that step 1 is the easiest because there is a lot of work done there, so you just need to choose the most fit for your problem. Although, there is still many open problems here to solve like the famous log-rank conjecture. The second step depends in the duality between the studied norms. The objective here is to avoid dealing with forall quantifiers (minimization), and solve the problem for existential quantufiers (maximization). This is because it's easier to just give a witness for the program, rather that showing that for all inputs the solution is optimal. The final step requires a witness for the resulting program. This could also be very difficult, because choosing a bad witness (one that is too far from the global optimum) could give a very weak or trivial lower bound. In the paper, the authors show how to choose a good witness for a particular case. Only for very few cases we know how to choose a good witness, and more research is needed in this part.

The paper ommits models like SMP (simultaneous message passing), unbounded-error protocols, and quantum communication with entanglement. The authors concentrate in lower bounds that can be stated in terms of a mathematical program by using norms. Still, they give a nice explanation on the corruption bound. This is an important technique because as noted by the authors it is the only lower bound technique that can separate quantum from randomized communication for total functions.