Contributions to the study of probabilistic communication complexity classes

Abstract

The focus of this work is on two problems in Communication Complexity Theory, both related to notions of communication complexity involving randomisation. First, we investigate the effect of the amount of correlation between the marginals of a bipartite distribution on the distributional complexity of a problem under that distribution. In this context we prove tight bounds on the distributional complexity under distributions with bounded mutual information in the case of the Disjointness problem. Second, we present new results regarding a three-decades-old open problem of Babai et al. (L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory. In Proceedings of the 27th IEEE FOCS, pages 337-347, 1986), who conjectured that the complexity classes UPP-cc and PSPACE-cc are incomparable. We prove that if a certain conjecture about hyperplane arrangements holds, then UPP-cc is a subset of PSPACE-cc. To support our geometric conjecture, and with the aim of proving it, we develop a theory of operations which are invariant with respect to the combinatorial structure of hyperplane arrangements, and use it to devise an algorithm which provides numerical evidence supporting our conjecture.