UCLA

Communication is a universal process by which two or more individuals exchange information. A communication task that we study involves two (or more) parties, each given their own private input, trying to solve a function f or other computational task on their inputs together. For example, distributed data centers routinely check consistency with each other. An important feature of common communication phenomena is that it is interactive. The parties communicate alternatively and adaptively. This feature is absent in the classical information theory which focuses on one-way transmissions. However, the questions studied in the classical information theory remain valid and vital. For example, how do we minimize the communication cost for a certain communication task and how do we handle noise when it is present. From a historical point of view, theoretical computer scientists initiated the study of communication inspired mostly by complexity theory instead of information theory. The latter source of inspiration motivates many other important questions. For example, how much more power a communication protocol gains given resources like randomness, nondeterminism, or quantum entanglement, etc.

In this dissertation, we discuss three concrete problems regarding the above questions. In particular, we study the following three problems.

(i) What is the maximum noise rate that can be tolerated in interactive communication? Specifically, we study the general noise model of arbitrary substitutions, deletions, and insertions. We settle this problem by giving a coding scheme that tolerates the maximum noise rate. A combinatorial ingredient of our scheme is that of tree code. We prove the existence of a tree code with strong distance properties.

(ii) What is the maximum communication complexity of constant-depth and polynomial-size circuits? We obtain strong communication lower bounds, ruling out the possibility of designing efficient generic communication protocols to solve this important class of problems. Our proof centers around the analytical measures threshold degree and sign-rank. The technique we use settles a 50-year-old problem in threshold degree that has applications to other areas of theoretical computer science including circuits complexity and learning theory.

(iii) How much power does a communication protocol gain taking advantage of quantum mechanics? We give a near-optimal separation between quantum and classical communication complexity, exhibiting functions that require only O(\log n) bits of communication for quantum protocols but any classical protocol needs to essentially exchange the entire input. Our approach first studies the analogous problem in the query model, for which we are able to exhibit an optimal separation. These questions are broadly recognized as being central to understanding the phenomenon of quantum speedups.