A very important problem in quantum communication complexity is to show that there is, or isn?t, an exponential gap between randomized and quantum complexity for a total function. There are currently no clear candidate functions for such a separation; and there are fewer and fewer randomized lower bound techniques that are not known to extend to the quantum setting. Among these are some information theoretic proofs and more recently, the subdistribution bounds.
We introduce a new technique to this family, based on Kolmogorov complexity. In order to gain a better understanding of how these techniques differ from the family of techniques that follow from Linial and Shraibman?s recent work on factorization norms, all of which extend to the quantum setting, we take another look at a few of these information theoretic proofs. Our main tool is Kolmogorov complexity.
We use Kolmogorov complexity for three different things:
- give a general lower bound in terms of Kolmogorov mutual information
- prove an alternative to Yao?s minmax principle based on Kolmogorov complexity
- identify worst case inputs.
We show that our method implies the rectangle and corruption bounds, known to be closely related to the subdistribution bound. We apply our method to the hidden matching problem, a relation introduced to prove an exponential gap between quantum and classical communication. We then show that our method generalizes the VC dimension and shatter coefficient lower bound. In the second part, we compare one-way communication and simultaneous communication in the case of distributional communication complexity and improve the previous known result.
In these proofs, the intuition is mostly the same as the original proofs of these results. Nevertheless, we give what we believe to be more elementary proofs, and this allows us to improve some of the previous results.