FOCS 2011:

Cynthia Dwork:
The Promise of Differential Privacy.  
 
Kirk Pruhs:
Green Computing Algorithmics.  

Vinod Vaikuntanathan: 
Computing Blindfolded: New Developments in Fully Homomorphic Encryption.

Shafi Goldwasser:
Pseudo Deterministic Algorithms
(Piore Award Talk)


FOCS 2010:

Ketan Mulmuley:
Geometric Complexity Theory.

Mihai Patrascu:
How to Grow Your Lower Bounds.

Tim Roughgarden: 
How To Think About Mechanism Design.

Dan Spielman:
Laplacian Gems.
(Nevanlinna Prize Talk)  


FOCS 2009:

Richard Karp:
What Makes an Algorithm Great?

Mihalis Yannakakis:
Computational Aspects of Equilibria.

Noga Alon:
Disjoint paths, isoperimetric problems, and graph eigenvalues.

Manuel Blum:
Can (Theoretical Computer) Science come to grips with Consciousness? 


FOCS 2008:

Scott Aaronson:
The Polynomial Method in Quantum and Classical Computing.
         
Gagan Aggarwal and S. Muthukrishnan:
Theory of Sponsored Search Auctions.

Luca Trevisan:
Average-case Complexity.


FOCS 2007:

Terrance Tao:
Structure and randomness in combinatorics.

Dan Boneh:
A Brief Look at Pairings Based Cryptography.

Daniel Spielman:
Spectral Theory and its Applications.


FOCS 2006:

Richard Karp:
Theory of Computation as a Lens on the Sciences: The Example of Computational Molecular Biology.

Terry Sejnowski:
A critique of pure vision.

Jon Kleinberg:
The Emerging Intersection of Social and Technological Networks: Open Questions and Algorithmic Challenges.


FOCS 2005:

Subhash Khot:
On the Unique Games Conjecture.

Bernard Chazelle:
Algorithmic Techniques and Tools from Computational Geometry.

Mihalis Yannakakis:
Probability and Recursion.
(Knuth Prize Talk)

Celebration of Alan Frieze's 60th birthday:

Noga Alon:
The Frieze-Kannan Decomposition method and Grothendieck type inequalities.

Jeff Kahn:
Some correlation inequalities.
 
Mike Steele:
Minimum Spanning Trees and the Zeta Theorems.

Boris Pittel:
Bootstrap percolation on the random regular graph.
 
Ravi Kannan:
Low-Rank Approximations to Matrices and Tensors.
 
Colin Cooper:
The cover time of random walks on random graphs.
 
Aravind Srinivasan:
The Local Lemma for random variables with large support.
 
Eric Vigoda:
Simulated Annealing for the Permanent and Binary Contingency Tables.

Eli Upfal:
The Combinatorics of Sequencing by Hybridization.
 
Dimitris Achlioptas.
Clustering of solutions in random constraint satisfaction problems.
 
Andrei Broder:
Sampling Search Engine Results.
 
Richard M. Karp:
Geometric Optics, Linear Programming and Congestion in Sensornets.


FOCS 2004:

None


FOCS 2003:

Avrim Blum:
Machine Learning: My favorite results, directions, and open problems.

Dana Randall:
Mixing.

Eli Upfal:
Performance Analysis of Dynamic Network Processes.


FOCS 2002:

Oded Goldreich:
Zero-Knowledge.

Éva Tardos:
Approximation Algorithms: problems, techniques, and their use in game theory.

Salil Vadhan:
Randomness Extractors and their Many Guises.


FOCS 2001:

Christos Papadimitriou:
Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction.

Piotr Indyk:
Algorithmic Applications of Geometric Embeddings.

Madhu Sudan:
Coding Theory.


FOCS 2000:

Jeffrey D. Ullman:
Ordinary Skill in the Art.
(Knuth Prize Lecture)