CQT computer scientists doom protocol to repeat itself

CQT researchers Rahul, Penghui and Attila (from left to right) have shown that there is no shortcut to running some kinds of protocol in parallel.

Almost all questions in computer science boil down to: is there a better way to solve this problem? A natural companion question is, if we have to solve several instances of the same problem at the same time, is there a better way to do it than just to repeat the best algorithm for one instance many times in parallel?

CQT researchers Rahul Jain, Attila Pereszlényi and Penghui Yao have answered the latter question with a resounding no for a particular problem-solving approach known as 'bounded-round public-coin randomized communication'. The no applies to any function tackled with such protocols, saving other researchers the trouble of investigating individual cases.

"We have shown that there is nothing much more intelligent that you can do than repeat the best protocol for one instance, naively," says Rahul. The result, described in a preprint, has recently been accepted for presentation at the prestigious IEEE Symposium on Foundations of Computer Science (FOCS 2012). The annual conference, now in its 53rd year, will be held in October.

In the work, the researchers use two quantities to evaluate the performance of the protocol. One is the 'communication complexity'. This applies when a protocol assumes that two parties work collaboratively to solve the problem. The communication complexity describes how many bits the two parties must exchange to reach their solution. Minimising communication complexity is important in practical applications, for example to reduce the number of signals that must be sent between processors in a computer.

The second measure is the probability of getting the right answer. Computer scientists know that the communication complexity of a function can be reduced, sometimes significantly, if the two parties involved share some random numbers. The numbers are referred to as a public-coin. But the trade-off is that the process then won't always output the right result, meaning the protocol has some success probability p < 1. Because p can be made very close to 1 easily, randomization is often helpful.

Taking this scenario, the researchers consider the success probability for parallel instances of the problem. If the same protocol were run a number, say k, times independently in parallel, you would expect the success probability to multiply with each repetition: p x p x p ... k times = p^k. This leads to exponential deterioration in the success probability. Is there a cleverer way to do the computation, that gives an overall success probability better than p^k, if communication remains about k times what is required for single instance of the problem? This is the question the researchers answer with no. The negative result is of a type known as a 'direct product theorem'.

Direct product theorems in other models have found significant applications. Notable examples are Raz's parallel repetition theorem for two prover games which lead to limits being set for other problems and Yao's XOR lemma, which had several applications in circuit complexity.

The CQT team points out that their work builds on several previous results from CQT researchers, and that it leaves open two interesting questions. One concerns the 'bound' in the protocol they consider. Bounded-round public-coin randomized communication sets a limit on total number of message exchanges. In the researchers' proof, this bound affects both the total number of bits exchanged and the success probability of the protocol for k instances. It's not clear if it has to, and a result with no dependence on the bound would be considered significantly stronger.

The second question is about quantum communication. The protocols they analyse allow only classical communication. Researchers know that quantum communication can change the complexity of computations, but have few answers on what it means for such protocols. "The quantum case is wide open," says Rahul.

For more details, see the paper "A direct product theorem for bounded-round public-coin randomized communication complexity", arXiv:1201.1666. The article will later appear in the proceedings of IEEE FOCS.