Correlation in hard distributions in communication complexity

• المؤلفون الرئيسيون: Klauck, Hartmut, Bottesch, Ralph Christian, Gavinsky, Dmitry
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: English
• منشور في: 2018
• الموضوعات: Communication Complexity; Information Theory; DRNTU::Science::Mathematics
• الوصول للمادة أونلاين: https://hdl.handle.net/10356/87921; http://hdl.handle.net/10220/46886

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 comm...