Examiners: Gillat Kol (adviser), Bernard Chazelle, and Ran Raz
Readers: Mark Braverman, Matt Weinberg

Abstract:

Communication complexity is the study of how two or more parties with private inputs compute a function that depends on all their inputs. The scarce resource is communication, or the number of bits exchanged between the parties. Communication complexity naturally applies to settings with interaction between multiple parties, such as auction design and distributed computing. Surprisingly, it also applies to many superficially unrelated settings, such as streaming algorithms and data structures, as bounds on communication can often be translated into bounds on other resources of interest, such as the memory required by a streaming algorithm.

Much of the work in this dissertation is in the area of interactive coding, which studies communication complexity in the presence of noise. I describe my research in both two party interactive coding, where my work not only shows protocols resilient to a larger fraction of noise than the previous state-of-the-art, but also provides matching impossibility results ruling out protocols with higher noise resilience, and in multi-party interactive coding, where I give tight bounds for codes for several emergent distributed models, including the broadcast model, the radio network model, and the beeping model.

Another large part is dedicated to communication problems in auction design theory, where the participating parties have their own interests and may not follow the protocol unless incentivized to do so. A common theme of this part is establishing tight separations between different classes of auctions, and understanding how various aspects of an auction affect its communication complexity. These separations are shown for both welfare maximizing and revenue maximizing auctions, and are often the first quantitative separations to be shown for these problems.

Finally, I cover my work showing tight bounds on the memory requirement of streaming algorithms by analyzing the induced low-round communication protocols. These bounds are the first of their kind as they apply to algorithms that can take multiple passes over the input. They are also extremely general, and hold for a large class of natural streaming problems.