Correlation in hard distributions in communication complexity

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F15%3A00448831" target="_blank" >RIV/67985840:_____/15:00448831 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.544" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.544</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.544" target="_blank" >10.4230/LIPIcs.APPROX-RANDOM.2015.544</a>

Result language
angličtina
Original language name
Correlation in hard distributions in communication complexity
Original language description
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 studiedextreme 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.
Czech name
—
Czech description
—

Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
ISBN
978-3-939897-89-7
ISSN
1868-8969
e-ISSN
—
Number of pages
28
Pages from-to
544-572
Publisher name
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Place of publication
Dagstuhl
Event location
Princeton
Event date
Aug 24, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)