SODA 2011:

Timothy Chan:
Computational Geometry for Non-Geometers: Recent Developments on Some Classical Problems.

William Freeman:
Where Computer Vision Needs Help from Computer Science.

Bruce Reed:
Graph Colouring via The Probabilistic Method.


SODA 2010:

Cynthia Dwork:
Differential Privacy in New Settings.

Noam Nisan:
Google's Auction for TV Ads.

Emmanuel Candes:
The Power of Convex Relaxation: The Surprising Stories of Matrix Completion and Compressed Sensing.


SODA 2009:

Michael I. Jordan:
Combinatorial Stochastic Processes and Nonparametric Bayesian Modeling.

Yuval Peres:
The Unreasonable Effectiveness of Martingales (Beyond Concentration).

Volker Strassen:
Probability, Algorithms and Complexity.


SODA 2008:

Bonnie Berger:
Graph Algorithms for Biological Systems Analysis.

Andrei Broder:
Computational Advertising.

Persi Diaconis:
Shuffling Cards, Adding Numbers, and Symmetric Functions.


SODA 2007:

Maria Chudnovsky:
Testing for a Theta.

Philippe Flajole:
Analytic Combinatorics - A Calculus of Discrete Structures.

Monika R. Henzinger:
Combinatorial Algorithms for Web Search Engines - Three Success Stories.


SODA 2006:

Alan Frieze:
Random Graphs.

Larry Peterson:
A Strategy for Continually Reinventing the Internet.

Rakesh Vohra:
Predicting the 'Unpredictable'.


SODA 2005:

John Baez:
Loop Quantum Gravity.

Uriel Feige:
Rigorous Analysis of Heuristics for NP-hard Problems.

Micha Sharir:
The Interface Between Computational and Combinatorial Geometry.


SODA 2004:

Bernard Chazelle:
Who Says You Have to Look at the Input? The Brave New World of Sublinear Computing?

Raymond Laflamme:
Quantum Computing.

Peter Winkler:
How Random is the Human Genome?


SODA 2003:

Persi Diaconis:
Who Cares About Permanents?

S. Muthukrishnan:
Data Streams: Algorithms and Applications.

Ian H. Witten:
Browsing Around a Digital Library.


SODA 2002:

Kurt Mehlhorn:
The Theory Behind LEDA.

Bob Connelly:
The Virtues of Expanding Geometric Objects.


SODA 2001:

Udi Manber:
Serving Billions of Pages to Hundreds of Millions of People is Harder Than It Seems.

Christos Papadimitriou:
Game Theory, Algorithms, and the Internet.

Ronald L. Graham:
Guessing Secrets.


SODA 2000:

Robin Thomas:
Digraph Minors and Algorithms.

Vasek Chvátal:
Cutting Planes and the Traveling Salesman Problem.

Gene Myers:
The Whole Genome Assembly of Drosophila.