Steam-powered Turing Machine University of Washington Computer Science & Engineering
 Theory and Algorithms Research
 CSE Home  About Us    Search    Contact Info 




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.

The UW Theory Seminar.

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


Faculty


Dave Bacon
Quantum computing and quantum information science, fault-tolerant quntum computation.

Paul Beame
Computational complexity, lower bounds, proof complexity, data structures, satisfiability algorithms for efficient reasoning systems.


Aram Harrow
Quantum computing and quantum information.

Anna Karlin
Algorithms; computational aspects of game theory, economics, and auctions; theoretical issues in data mining and information retrieval.


Richard Ladner
Data compression, cache performance of algorithms, algorithms for media-on-demand systems.

James Lee
Combinatorics, geometry, and analysis, with applications to algorithms and complexity theory.


Anup Rao
Complexity theory, derandomization, combinatorics, coding theory.
Postdoctoral Researchers
Xin Li

Current Visitors
Manor Mendel, Bruce Shepherd

Graduate Students
Benjamin Birnbaum
L. Elisa Celis
Jessica Chang
Dimitrios Gklezakos
Alexander Jaffe
Daniel Poore
 Widad Machmouchi
Mohammad Moharrami
Cyrus Rashtchian
Makrand Sinha
Kevin Zatloukal


Some Recent Graduates

Cam Thach Nguyen, Dang-Trinh Huynh-Ngoc, Prasad Raghavendra (Georgia Tech), Gyanit Singh, Alice Neels, Jeremy Buhler (Washington University), Ioannis Giotis, Matt Cary (Google), Ning Chen (Nanyang Technological Institute), James Fix (Reed College), Justin Goshi (Timergent), Jason Hartline (Northwestern), Frank McSherry (Microsoft), Atri Rudra (University of Buffalo), Ashish Sabharwal (Cornell), Jared Saia (University of New Mexico), Tammy VanDeGrift (University of Portland), Erik Vee (Yahoo). More complete alumni list.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to Anup Rao]