Please use this identifier to cite or link to this item:
Title: Correlation in hard distributions in communication complexity
Authors: Klauck, Hartmut
Bottesch, Ralph Christian
Gavinsky, Dmitry
Keywords: Communication Complexity
Information Theory
Issue Date: 2015
Source: Bottesch, R. C., Gavinsky, D. & Klauck, H. (2015). Correlation in hard distributions in communication complexity. LIPIcs–Leibniz International Proceedings in Informatics, 40, 544-572. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.544
Series/Report no.: LIPIcs–Leibniz International Proceedings in Informatics
Abstract: We study the effect that the amount of correlation in a bipartite distribution has on the communication complexity of a problem under that distribution. We introduce a new family of complexity measures that interpolates between the two previously studied extreme cases: the (standard) randomised communication complexity and the case of distributional complexity under product distributions. - We give a tight characterisation of the randomised complexity of Disjointness under distributions with mutual information k, showing that it is Theta(sqrt(n(k+1))) for all 0 <= k <= n. This smoothly interpolates between the lower bounds of Babai, Frankl and Simon for the product distribution case [k=0], and the bound of Razborov for the randomised case. The upper bounds improve and generalise what was known for product distributions, and imply that any tight bound for Disjointness needs Omega(n) bits of mutual information in the corresponding distribution. - We study the same question in the distributional quantum setting, and show a lower bound of Omega((n(k+1))^{1/4}), and an upper bound (via constructing communication protocols), matching up to a logarithmic factor. - We show that there are total Boolean functions f_d that have distributional communication complexity O(log(n)) under all distributions of information up to o(n), while the (interactive) distributional complexity maximised over all distributions is Theta(log(d)) for n <= d <= 2^{n/100}. This shows, in particular, that the correlation needed to show that a problem is hard can be much larger than the communication complexity of the problem. - We show that in the setting of one-way communication under product distributions, the dependence of communication cost on the allowed error epsilon is multiplicative in log(1/epsilon) - the previous upper bounds had the dependence of more than 1/epsilon. This result, for the first time, explains how one-way communication complexity under product distributions is stronger than PAC-learning: both tasks are characterised by the VC-dimension, but have very different error dependence (learning from examples, it costs more to reduce the error).
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.544
Rights: © 2015 Ralph Christian Bottesch, Dmitry Gavinsky, and Hartmut Klauck; licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
Correlation in hard distributions in communication complexity.pdf649.32 kBAdobe PDFThumbnail

Citations 20

Updated on Sep 6, 2020

Page view(s)

Updated on Jun 25, 2022

Download(s) 50

Updated on Jun 25, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.