Summary | Rationale | Powerpoint | JPG Slide | JPG Image | Credits | Comments | All Nuggets
Algorithms Research: design new approaches to solve computing problems.
Computational Complexity Theory: prove no good algorithms exist.
The two efforts complement and inform each other.
As computing architectures evolve, or applications and data models change, both areas adapt to them. Thus they are living sciences.
Classical examples: NP-completeness and PSPACE-completeness (explain difficulty of combinatorial search and the difficulty of finding good strategies in games).
But algorithms and complexity have evolved to meet challenges in every aspect of computing: data streaming, algorithms that compute approximate solutions (and its associated complexity theory), online computation, strategic interactions, etc.
Trying to prove that algorithms for certain tasks (in whatever model) do not exist is an important complement to design of algorithms, and often provides valuable insights into the problem. For instance, the potentially exponential speedup of quantum computing over standard computing (Shor's algorithm) was discovered as part of the process of trying to prove lowerbounds.
Another area with close connection between algorithms and complexity is the study of approximability of NP-hard optimization problems. The process of discovering new algorithms and that of showing (assuming P \neq NP) the nonexistence of algorithms has gone hand in hand in the past 15 years.
The working group on complexity: Luca, Valentine, Avi, Leonid, Sanjeev.
List ideas for possible images. You can also upload images you've found using a command like this Δ.
