Communication Complexity: For Coding, Commerce, and Currents

Abstract

Since its introduction in Yao's seminal paper [Yao79], communication complexity has revolutionized theoretical computer science. Indeed, not only has communication complexity been successful in areas where communication is an important resource, but it has also resulted in breakthroughs in areas that seemingly have nothing to do with communication! This is because bounds on communication can often be translated into bounds on other resources of interest, such as memory usage and circuit size. As the title suggests, we consider the role of communication complexity in the study of three different areas in theoretical computer science: Coding: Part I is about interactive error correcting codes, used to make interactive protocols resilient to noise. I study the noise tolerance of popular two-party and multi-party communication channels, constructing communication efficient codes with high noise tolerance for some of these channels, and proving that noise tolerance implies large communication overheads for others. Commerce: Part II studies communication problems in auction design, 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. Currents: Part III covers my work on the memory requirement of graph streaming algorithms, which are algorithms whose input is a massive graph that they can only scan a few times. While algorithms that scan their input once are by now well understood, the situation is different for multi-pass streaming algorithms, which are the focus of this part of the thesis. Interestingly, each of these areas imposes additional requirements on the classical model of communication complexity: in interactive coding, we study communication complexity under noise; in auction design, we study communication complexity with incentives; and in multi-pass streaming, we consider communication complexity with few rounds of communication. While these three topics are seemingly very different, they all have strong connections with communication complexity, and studying them together often leads to deep insights.