Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/49156
DC Field | Value | |
---|---|---|
dc.title | Studies in Communication Complexity and Semidefinite Programs | |
dc.contributor.author | PENGHUI YAO | |
dc.date.accessioned | 2014-01-31T18:01:25Z | |
dc.date.available | 2014-01-31T18:01:25Z | |
dc.date.issued | 2013-09-03 | |
dc.identifier.citation | PENGHUI YAO (2013-09-03). Studies in Communication Complexity and Semidefinite Programs. ScholarBank@NUS Repository. | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/49156 | |
dc.description.abstract | This thesis contains two independent parts. The first part concerns fast parallel approximation algorithms for semidefinite programs. The second part concerns strong direct product results in communication complexity. In the first part, we study fast parallel approximation algorithms for certain classes of semidefinite programs. In Chapter 3, we present a fast parallel approximation algorithm for positive semidefinite programs. In Chapter 4, we present a fast parallel approximation algorithm for mixed packing and covering semidefinite programs. In the second part, we are concerned with strong direct product theorems in communication complexity. In Chapter 6, we show a direct product theorem for any relation in the model of two-party bounded-round public-coin communication complexity. In Chapter 7, we show a strong direct product theorem for all relations in terms of the smooth rectangle bound in the model of two-way public-coin communication complexity. | |
dc.language.iso | en | |
dc.subject | semidefinite programs, parallel computation, communication complexity, strong direct product theorems, smooth rectangle bound, information theory | |
dc.type | Thesis | |
dc.contributor.department | CENTRE FOR QUANTUM TECHNOLOGIES | |
dc.contributor.supervisor | RAHUL JAIN | |
dc.description.degree | Ph.D | |
dc.description.degreeconferred | DOCTOR OF PHILOSOPHY | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Ph.D Theses (Open) |
Show simple item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
YaoP.pdf | 1.09 MB | Adobe PDF | OPEN | None | View/Download |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.