18.419 Seminar in Theoretical Computer Science: Random walks and polynomial-time algorithms.

Tentative Schedule.

Tue, Feb 5. Algorithms based on random walks.

Thu, Feb 7. A1: Convex optimization I.

Tue, Feb 12. Convex optimization II.

Thu, Feb 14. Basic parameters.

Thu, Feb 21. Isoperimetric coefficients and mixing times.

Tue, Feb 26. Conductance.

Thu, Feb 28. Canonical Paths.

Tue, Mar 5. A2: Approximate Counting.

Thu, Mar 7. Approximating the permanent (Mihai).

Tue, Mar 12. A3: Counting Knapsack solutions (Grant/Steve).

Thu, Mar 14. Coupling.

Tue, Mar 19. A4: Counting Colorings (Chris/Fumei).

Thu, Mar 21. A5: Computing the volume.

Tue, Apr 2. Random walks in continuous spaces.

Tue, Apr 9. The Localization Lemma (Bobby).

Thu, Apr 11. Isoperimetric inequalities (Rados).

Apr 18, 23. The ball walk.

Apr 25, 30. Hit-and-run.

Thu, May 2. Average Conductance (Jan/Prahladh).

Tue, May 7. Open problems.

May 9, 14, 16. Project presentations.