Studies in Communication Complexity and Semidefinite Programs

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.