Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBottesch, Ralph Christian
dc.identifier.citationBottesch, R. C. (2016). Contributions to the study of probabilistic communication complexity classes. Doctoral thesis, Nanyang Technological University, Singapore.
dc.description.abstractThe 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.en_US
dc.format.extent126 p.en_US
dc.titleContributions to the study of probabilistic communication complexity classesen_US
dc.contributor.supervisorHartmut Klaucken_US
dc.contributor.schoolSchool of Physical and Mathematical Scienceen_US​Doctor of Philosophy (SPMS)en_US
item.fulltextWith Fulltext-
Appears in Collections:SPMS Theses
Files in This Item:
File Description SizeFormat 
ralph_bottesch_phd_thesis_20160223.pdfDoctoral thesis622.09 kBAdobe PDFThumbnail

Google ScholarTM


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