Kolmogorov complexity and combinatorial methods in communication complexity
| Autor: | Sophie Laplante, Marc Kaplan |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
Discrete mathematics
Information theory General Computer Science Kolmogorov complexity Communication complexity Mutual information Upper and lower bounds Theoretical Computer Science Combinatorics VC dimension Chain rule for Kolmogorov complexity Kolmogorov structure function Computer Science(all) Mathematics |
| Zdroj: | Theoretical Computer Science. 412:2524-2535 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2010.10.044 |
| Popis: | We introduce a method based on Kolmogorov complexity to prove lower bounds on communication complexity. The intuition behind our technique is close to information theoretic methods.We use Kolmogorov complexity for three different things: first, to give a general lower bound in terms of Kolmogorov mutual information; second, to prove an alternative to Yao’s minmax principle based on Kolmogorov complexity; and finally, to identify hard 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 bounds. Finally, we compare one-way communication and simultaneous communication in the case of distributional communication complexity and improve the previous known result. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect