APPROX plenary speaker: Anupam Gupta (NYU)
Going Beyond the Worst Case in Approximation/Online Algorithms
While analyzing algorithms in the worst-case has long served us well, recent years have seen an exciting surge in analyzing algorithms in models that go beyond the worst case. I will discuss some of the results and techniques that come out of this endeavor. My focus will be on three questions: How do we maintain small covers for a set of elements arriving online? How do we do load-balancing near-optimally when we have a small sample of the upcoming data? And what guarantees on the performance of the well-known A-star algorithm? I will try to keep the talk as self-contained as possible.
RANDOM plenary speaker: Mark Jerrum (Queen Mary University of London)
Modern Mixing, Spatial and Temporal
The last five years have seen a revolution in the analysis of the mixing time of Markov chains. It is now possible to prove optimal upper bounds on mixing time for a wide variety of Markov chains, for example the bases-exchange random walk for arbitrary matroids, or Glauber dynamics for the hard-core model in the uniqueness phase. In some instances, no sub-exponential upper bound was previously known. The new ideas that have powered this revolution are strikingly novel, but their working out is often highly technical. I will present recent advances from the point of view of the user. The mixing time bounds can often be packaged in a simple form that hides the technical complexities underneath.