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:

???


RANDOM 2002:

Michael Mitzenmacher:
New Directions in Balls and Bins Problems.

Dan Spielman:
The Smoothed Analysis of Algorithms.

Joel Spencer:
Phase Transitions for Random Processes.


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. 


ICALP RANDOM 2000:

Samson Abramsky:
Game Semantics: Achievements and Prospects.  

Gregor Engels:
Graph Transformation as Unifying Formal Framework for System Modeling and Model Evolution. 

Johan Hastad:
Which NP-hard optimization problems admit non-trivial efficient approximation algorithms? 

Roberto Gorrieri:
Non Interference for Analysis of Cryptographic Protocols. 

Zohar Manna:
Alterating Verification Diagrams.  

Kurt Mehlhorn:
Graph Algorithms and Constraint Programming. 

Oded Goldreich:
Pseudorandomness.

Andrei Broder:
Min-wise Independent Permutations: Theory and Practice.