RANDOM APPROX 2011:

Joel Spencer:
Two Needles in Exponential Haystacks

David Williamson:
Some Open Problems in Approximation Algorithms


RANDOM APPROX 2010:

Leslie A Goldberg:
Approximating the Tutte polynomial of a graph

Oded Goldreich:
Some Thoughts regarding Unconditional Derandomization


RANDOM APPROX 2009:

Prabhakar Raghavan:
Special tribute session to Rajeev Motwani


RANDOM APPROX 2008:

Nathan Linial:
???

Harald R?cke:
???

Anup Rao:
???


RANDOM APPROX 2007:

Sanjeev Khanna:
Disjoint Paths in Networks.

Rocco Servedio:
Learning, Testing, and Approximation.

Charles Fefferman:
Interpolation of C^m Functions in n dimensions.


RANDOM APPROX 2006:

Nick Wormald:
Analysis of algorithms on the cores of random graphs. 

Johan Håstad:
On non trivial approximations of CSPs.


RANDOM APPROX 2005:

Alistair Sinclair:
???


RANDOM APPROX 2004:

Madhu Sudan:
Sublinear Time Algorithms in Coding Theory.

Vijay Vazirani:
Solvency Games: How to Gamble Forever. 


RANDOM APPROX 2003:

???


APPROX ESA 2002:

William Cook: 
Solving Traveling Salesman Problems. 

Tamal K. Dey: 
Computing Shapes from Point Cloud Data. 

Anna R. Karlin: 
Mechanism Design for Fun and Profit. 
 
Mikkel Thorup: 
On Distance Oracles and Routing in Graphs

Yuval Rabani:
Search and Classification of High Dimensional Data. 

R. Ravi:
Bicriteria Spanning Tree Problems. 

Gene Myers:
???

Christos Papadimitriou:
???

Ehud Shapiro:
???


RANDOM APPROX 2001:

Michel X. Goemans: 
Using Complex Semidefinite Programming for Approximating MAX E2-LIN3. 

Russell Impagliazzo: 
Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems. 

Anna R. Karlin: 
Web Search via Hub Synthesis. 

Luca Trevisan: 
Error-Correcting Codes and Pseudorandom Projections. 

Salil P. Vadhan: 
Order in Pseudorandomness. 


APPROX ESA 2000:

Sanjeev Arora: 
Approximation algorithms that take advice. 

Dorit S. Hochbaum: 
Instant recognition of polynominal time solvability, half integrality and 2-approximations. 

Rolf H. Möhring: 
Scheduling under uncertainty: Optimizing against a randomizing adversary. 

David B. Shmoys: 
Approximation algorithms for facility location problems. 

Monika Rauch Henzinger: 
Web Information Retrieval - an Algorithmic Perspective. 

Thomas Lengauer: 
Computational Biology - Algorithms and More.