|
Theory and Algorithms Research
|
|
Theory at UW
[Faculty]
[Research Topics]
[Courses]
[Affiliates & visitors]
[Graduate Students]
[Recent Graduates]
Overview:
Theoretical computer science aims to understand the nature of
efficient computation. This is important not only for the pervasive
role that computers play in today's society, but also for purely
foundational reasons --- theory helps us map the potential and limits
of what nature permit us to solve quickly, and which problems are
truly beyond the realm of solvability (regardless of Moore's law or
other short term technological improvements). Theory of computation gives
a way to exploit tractability via a choice of several powerful
algorithmic techniques. It also provides a formalism for identifying and
quantifying intractability, coping with it (eg., using approximation
algorithms and provable heuristics), and even putting intractability
to work for us such as in crytography and random number generators.
Today, research in theory is thriving, with long standing open
questions being solved at regular intervals. In addition, the field is
ever-evolving and ready to take on new challenges raised by new
computing phenomena (such as the internet, large peer-peer networks, massive data sets). The dynamism and innovative thinking of the field has led
to whole new areas such as quantum computing, computational aspects of
game theory and economics, algorithms for large scale networks,
streaming computation, etc. There is also lot of conceptual progress,
and unsuspected connections between seemingly disparate areas continue
to emerge and clarify our picture of the computational landscape.
The theory group at UW has interests and expertise in most active
areas of current research within theory. The collaborative environment
within the department fosters exchange of ideas not just within the
theory group, but also enables, on a consistent basis, extremely
productive and successful collaborations that apply theory to new
application areas and the present-day computing challenges.
External to the department, too, Seattle provides a great environment
to do theory (and this isn't just because of the coffee!). The theory and crypto groups at Microsoft
Research are invaluable resources -- on top of research
collaborations, we benefit from their innumerable seminars
and the advanced theory courses their members often offer at UW.
- Dave Bacon: Quantum computing and quantum information science, fault-tolerant quantum computation.
- Paul Beame: Computational complexity, lower bounds, proof
complexity, data structures, satisfiability algorithms for efficient
reasoning systems.
- Venkatesan Guruswami: Theory of error-correcting codes,
approximability of NP-hard problems, complexity theory, algebraic
algorithms.
- 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.
Recent visitors and postdocs
More complete alumni list.
(These pages give an idea of the varied research activities, but are not always updated with the latest developments and results. Refer to individual faculty member and graduate student webpages for the latest results and papers on a particular topic.)
- Theory-Night: Theory night is about UW CSE theory students getting together for 2-3 hours one evening a week to discuss and solve theory problems.
- Approximate solutions to NP-hard problems Our goal is to understand how well NP-hard optimization problems can be solved if one settles for approximate solutions with provable performance guarantees.
- Auctions: The goal of auction research is to construct auction mechanisms that are a good replacement for non-adaptive selling mechanisms such as fixed pricing with market analysis.
- Computational Biology This project addresses a wide variety of algorithmic problems related to mapping and sequencing of genomes, discovery of significant signals in DNA and protein sequences, design of DNA microarrays, analysis of expression data, and neurally inspired computing.
-
Error-Correcting Codes
The focus of this research is on constructions of error-correcting codes and efficient algorithms for decoding them in the presence of large amounts of noise, as well as exploring connections of codes to complexity theory and cryptography.
- Proof Complexity This project studies the sizes of proofs needed to verify propositional
tautologies (and other co-NP-complete problems) in various proof systems.
- Time-Space Tradeoffs This project examines the tradeoffs between
the time and space that any algorithm needs to use to solve natural
computational problems.
- Modern Data Structures This project studies theoretical implications for data structures of the power of processors to execute instructions that
operate on single words of data at unit cost.
- Spectral Analysis: The eigenstructure of data sets has shown empirical
promise in data mining. We study such approaches formally, with an eye
towards performance in a realistic environment.
-
Cache Performance of Algorithms We study how architecural considerations influence the performance of algorithms.
-
Algorithms for Media-on-Demand In this project we investigate the ability of stream merging to help solve the bandwidth problems for multimedia.
We have a regular theory seminar on Tuesday afternoons.
We also offer a variety of advanced theory courses (roughly one per quarter). Some recent ones:
|
 |
Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to venkat]
|
CSE Home