CAREER: Information Theoretic Methods in Communication and Computational Complexity

Dartmouth College, Hanover NH

Investigators

Abstract

From the very early years of computer science it has been clear that computational problems vary greatly in difficulty, ranging from easy to moderately hard to intractably hard to outright unsolvable. Computational complexity theory is the branch of computer science that seeks to rigorously and mathematically study the inherent difficulty of computational problems, measured as the amount of a certain resource (or resources) required for their solution, and organize problems into classes based on their inherent difficulty. Examples of relevant resources include processing time, storage space and inter-computer communication. Communication complexity involves the latter resource and asks how many bits must be communicated between different computers to solve a problem whose input is split between these computers. There is plenty of intrinsic interest in communication complexity, because of the large variety of Internet-driven applications where it is relevant. In addition, over the last decade and a half, communication complexity has been emerging as an area that unites many seemingly disparate areas of theoretical computer science some of which do not directly involve communication; examples are circuit complexity, query complexity, quantum computing, algorithmic game theory, optimization and distributed computing. In recent years, information theory has proved itself to be a powerful tool in the study of communication complexity, and therefore in the various other areas of complexity theory that communication impacts. I have already explored this theme in my recent work and was an author of a recent paper that formally introduced the concept of information complexity and described its relation to communication complexity. Other subsequent work of mine has applied information theoretic techniques to prove theorems about communication complexity and applied these theorems in turn to explore the inherent difficulty of problems not directly involving communication. The main goal of this project is to continue this line of work in two ways. First, I shall continue to develop and extend what I call the information complexity framework and attempt to apply it to models of computation where it hasn't yet been applied successfully. A noteworthy subgoal of the first goal will be to use this framework to understand the limitations of quantum computation. Second, I shall seek to study certain concrete problems in communication complexity that have known connections to other areas of complexity theory. Two specific areas I shall focus on are (1) the complexity of data stream computations and (2) circuit complexity, with an emphasis on the power of shallow circuits.