| Sept 16 |
Thomas P. Hayes, Toyota Technological Institute at Chicago
Markov Chains for Randomly Coloring Graphs |
| Sept 30 |
R. Ravi, Carnegie Mellon University
Approximation Algorithms for Stochastic Integer Programs |
| Oct 11-14 |
FOCS |
| Fri Oct 17 |
NE43-518, 4:15pm
Dorit Aharonov, The Hebrew University and U.C. Berkeley
Approximating the Shortest and Closest Vectors in a Lattice to within Sqrt(n) lie in NP Intersect Co-NP |
| Oct 21 |
Sariel Har-Peled, University of Illinois Urbana-Champaign
On Coresets and Shape Fitting in High Dimensions |
| Oct 28 |
Assaf Naor, Microsoft Research
Quadratic Relaxation via Grothendieck's Inequality |
| Wed Oct 29 |
NE43-518, 4:15pm
Irit Dinur, U. C. Berkeley
PCP Testers: Towards a Combinatorial Proof of the PCP Theorem |
| Wed Nov 12 |
NE43-518, 4:15pm
Sanjeev Arora, Princeton University
Expander Flows and a Sqrt(log n)-Approximation for Graph Expansion/Sparsest Cut |
| Nov 18 |
Michael Kearns, University of Pennsylvania
Network Models for Game Theory and Economics |
| Nov 25 |
Daniel Stefankovic, University of Chicago
Simultaneous Diophantine Approximation with Excluded Primes |
| Dec 2 |
Philip Klein, Brown University
Multiple-Source Shortest Paths in Planar Graphs Allowing Negative Lengths |
| Wed Dec 10 |
NE43-941, 3:15pm (refreshments at 3pm)
Alistair Sinclair, U. C. Berkeley and Microsoft Research
Phase Transitions, Mixing Times and the Ising Model on Trees |
