Correlation in hard distributions in communication complexity
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...
Saved in:
Main Authors: | Klauck, Hartmut, Bottesch, Ralph Christian, Gavinsky, Dmitry |
---|---|
其他作者: | School of Physical and Mathematical Sciences |
格式: | Article |
語言: | English |
出版: |
2018
|
主題: | |
在線閱讀: | https://hdl.handle.net/10356/87921 http://hdl.handle.net/10220/46886 |
標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
機構: | Nanyang Technological University |
語言: | English |
相似書籍
-
The complexity of quantum disjointness
由: Klauck, Hartmut
出版: (2018) -
New bounds for the garden-hose model
由: Klauck, Hartmut, et al.
出版: (2018) -
Contributions to the study of probabilistic communication complexity classes
由: Bottesch, Ralph Christian
出版: (2016) -
The partition bound for classical communication complexity and query complexity
由: Jain, R., et al.
出版: (2013) -
EXPLORING DIFFERENT MODELS OF QUERY COMPLEXITY AND COMMUNICATION COMPLEXITY
由: SUPARTHA PODDER
出版: (2016)