Please use this identifier to cite or link to this item:
Title: Contributions to the study of probabilistic communication complexity classes
Authors: Bottesch, Ralph Christian
Keywords: DRNTU::Science::Mathematics
Issue Date: 2016
Source: Bottesch, R. C. (2016). Contributions to the study of probabilistic communication complexity classes. Doctoral thesis, Nanyang Technological University, Singapore.
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.
DOI: 10.32657/10356/66033
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Theses

Files in This Item:
File Description SizeFormat 
Doctoral thesis622.09 kBAdobe PDFThumbnail

Google ScholarTM




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