Theory of Computation

Theoretical computer science aims to understand the nature of efficient computation. The goal is to map the potential and limits of which tasks can be completed quickly and which are truly beyond the realm of solvability (regardless of short term technological improvements). We are interested both in developing new algorithmic techniques and identifying and coping with intractability.

The theoretical study of computer science is constantly evolving to take on new challenges raised by new computing phenomena (such as the internet, large peer to peer networks, massive data sets). Recent decades have seen the rise of new areas, such as quantum computing, computational aspects of game theory and economics, algorithms for large scale networks, and streaming computation. Unsuspected connections between seemingly disparate areas continue to emerge and clarify our picture of the computational landscape.

Seattle provides a great environment to do theory. Our proximity to the theory and crypto groups at Microsoft Research is a big bonus. We benefit from their seminars and the advanced theory courses their members often teach at UW. The UW-MSR Theory Center solidifies the collaboration.

Sign up for the theory-students mailing list or sign up for the theory-group mailing list.