More Good FOCS Fodder

Another cool paper on the arXiv today, this time by Iordanis Kerenidis(MIT)

Quantum multiparty communication complexity and circuit lower bounds
Iordanis Kerenidis
We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result of our simulation, we show that if the quantum k-party communication complexity of a function f is $Omega(n/2^k)$, then its classical k-party communication is $Omega(n/2^{k/2})$. Finding such an f would allow us to prove strong classical lower bounds for (k>log n) players and hence resolve a main open question about symmetric circuits. Furthermore, we prove that for the Generalized Inner Product (GIP) function, the quantum model is exponentially more efficient than the classical one. This provides the first exponential separation for a total function between any quantum and public coin randomized communication model.

The first part of the abstract refers to one of the grand hopes of the field of communication complexity: to prove that a function cannot be computed with ACC circuits (constant depth, polynomial size, circuits with unbounded fan-in, and mod gates.) It turns out that finding such an f corresponds to proving a superlogarithmlic lower bound for a k-party communication complexity problem. What Iordanis does is show an explicit connection between lower bound between classical multiparty communication complexity results and quantum multiplarty communication complexity. The hope here is then that the proofs in the quantum world will turn out to be simpler than in the classical world, where all attempts to get functions out of ACC have failed. Did we ever imagine there would be a day when the quantum world was considered simpler than the classical world? Yeah for the new generation.
In the second part of the paper, Iordanis shows an exponential separation between classical communication complexity and quantum communication for a total function. A total function is a function which is defined over all of it’s inputs. Previously all the functions for which there was an exponential separation were promise problems or relations. This is quite cool for the world of communication complexity. This follows earlier work by Iordanis and coworkers Ziv Bar-Yossef and T.S. Jayram where they were able to show an exponential quantum-classical separation for a communication complexity problem which used only one way communication. Quite a roll to be on!