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.

Please report errors in award information by writing to: awardsearch@nsf.gov.