The members of the complexity theory group are all interested, in one way or another, in the limitations of computation: What problems are not feasible to solve on a computer? How can the infeasibility of a problem be used to rigorously construct secure cryptographic protocols? What problems cannot be solved faster using more machines? What are the limits to how fast a particular problem can be solved or how much space is needed to solve it? How do randomness, parallelism, the operations that are allowed, and the need for fault tolerance or security affect this?
There is great beauty in theoretical computer science. It is exciting to discover what makes a particular problem difficult, to find a provably optimal solution to a problem, or to discover unexpected connections between seemingly unrelated problems. Theoretical computer science provides important new ways of thinking about computation and provides lasting insights that are applicable to a wide variety of systems. There are also great challenges and opportunities since so many basic problems remain unsolved.
Faculty
Allan BorodinMark Braverman
Stephen Cook
Faith Ellen
Vassos Hadzilacos
Mike Molloy
Toniann Pitassi
Charles Rackoff
Sam Toueg
Vinod Vaikuntanathan