Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/49156
Title: | Studies in Communication Complexity and Semidefinite Programs | Authors: | PENGHUI YAO | Keywords: | semidefinite programs, parallel computation, communication complexity, strong direct product theorems, smooth rectangle bound, information theory | Issue Date: | 3-Sep-2013 | Citation: | PENGHUI YAO (2013-09-03). Studies in Communication Complexity and Semidefinite Programs. ScholarBank@NUS Repository. | 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. | URI: | http://scholarbank.nus.edu.sg/handle/10635/49156 |
Appears in Collections: | Ph.D Theses (Open) |
Show full 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.