Contributions to the study of probabilistic communication complexity classes
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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2016
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/66033 |
| _version_ | 1811679082909270016 |
|---|---|
| author | Bottesch, Ralph Christian |
| author2 | Hartmut Klauck |
| author_facet | Hartmut Klauck Bottesch, Ralph Christian |
| author_sort | Bottesch, Ralph Christian |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T03:03:30Z |
| format | Thesis |
| id | ntu-10356/66033 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:03:30Z |
| publishDate | 2016 |
| record_format | dspace |
| spelling | ntu-10356/660332023-02-28T23:34:46Z Contributions to the study of probabilistic communication complexity classes Bottesch, Ralph Christian Hartmut Klauck School of Physical and Mathematical Sciences DRNTU::Science::Mathematics 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. DOCTOR OF PHILOSOPHY (SPMS) 2016-03-03T04:16:58Z 2016-03-03T04:16:58Z 2016 Thesis Bottesch, R. C. (2016). Contributions to the study of probabilistic communication complexity classes. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/66033 10.32657/10356/66033 en 126 p. application/pdf |
| spellingShingle | DRNTU::Science::Mathematics Bottesch, Ralph Christian Contributions to the study of probabilistic communication complexity classes |
| title | Contributions to the study of probabilistic communication complexity classes |
| title_full | Contributions to the study of probabilistic communication complexity classes |
| title_fullStr | Contributions to the study of probabilistic communication complexity classes |
| title_full_unstemmed | Contributions to the study of probabilistic communication complexity classes |
| title_short | Contributions to the study of probabilistic communication complexity classes |
| title_sort | contributions to the study of probabilistic communication complexity classes |
| topic | DRNTU::Science::Mathematics |
| url | https://hdl.handle.net/10356/66033 |
| work_keys_str_mv | AT botteschralphchristian contributionstothestudyofprobabilisticcommunicationcomplexityclasses |