Please use this identifier to cite or link to this item: http://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
Source: 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 SizeFormatAccess SettingsVersion 
YaoP.pdf1.09 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

180
checked on Apr 21, 2018

Download(s)

133
checked on Apr 21, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.