Randomized Algorithms
Date: Tuesdays and Thursdays, 3-4:30 pm in ES&T 1105
Instructor: Eric Vigoda
The book by
Mitzenmacher and Upfal might be useful, especially if
you want extra background material.
Some of the topics I expect to cover aren't in the book.
Homework
Lecture schedule
- Lecture 1 (Jan 10) -- Karger's Min-cut algorithm:
notes;
[Karger] and
improvement of [Karger/Stein]
Read Chapter 1 of [Mitz/Upfal] for extra background
- Lecture 2,3 (Jan 12,17) -- #DNF and Network Unreliability:
notes;
[Karger]
Chapter 10 of [Mitz/Upfal] has a different approach for #DNF.
Related project idea --
Deterministic approximation of #DNF in O(exp(log4n)) time
[Luby/Velickovic/Wigderson]
- Lecture 4 (Jan 19) --
Review of Chernoff bounds: see Chapter 4 in [Mitz/Upfal]
Related project idea -- Improved deviation bounds by
[Kim/Vu],[Vu]
- Lecture 5 (Jan 24) -- Hypergraph 2-coloring, aka Property B
notes;
[Radhakrishnan/Srinivasan]
- Lecture 6 (Jan 26) -- Balls and Bins, power of 2 choices:
notes;
See Chapters 5 and 14 of [Mitz/Upfal]
Related project idea --
Improved power of 2 choices
[Vocking]
Related project idea --
Many more balls than bins
[Berenbrink et al]
- Lecture 7 (Jan 31) -- Derandomization: Conditional Expectation and
Pairwise Independence
See Chapters 6.1-6.3 and 13.1 of [Mitz/Upfal]
- Lecture 8 (Feb 2) -- Application of Pairwise Independence: Maximal Independent Sets;
notes
See notes by Luby and Wigderson
for some complexity applications of pairwise independence.
- Lecture 9 (Feb 7) -- More Applications of Pairwise Independence:
Probability Amplification
and 2-Universal Hash Functions
See Chapter 13.2-13.3 of [Mitz/Upfal]
- Lecture 10 (Feb 9) --
Sampling and Counting Relationship: Approximating #Knapsack; notes;
[Dyer]'s original paper
- Lecture 11 (Feb 14) --
Random k-SAT
- Lecture 12 (Feb 16) --
Electrical resistance and cover times
- Lecture 13 (Feb 21) --
Permanent of random matrices
- Lecture 14 (Feb 23) --
Markov chains;
Ergodic -> Unique stationary distribution;
notes
See Chapter 7 of [Mitz/Upfal]
- Lecture 15 (Feb 28) --
Coupling method for analyzing Markov chains;
Applications of coupling
See Chapter 11 of [Mitz/Upfal]
- Lecture 16 (Mar 2) --
Approximating the permanent
See
this chapter by Jerrum(especially Section 5.3) and
these notes
- Lecture 17 (Mar 7) --
Lovasz Local Lemma
and Application of LLL to packet routing
- Lecture 18 (Mar 9) --
Identity Testing;
Perfect Matchings
- Lecture 19 (Mar 14) --
Probability amplification by random walks on expanders
See notes from class by
by Linial and Wigderson on expander graphs
- March 16 class cancelled
- Lecture 20 (Mar 28) --
Seminar by Santosh Vempala in MiRC 102
Intro to algorithms for estimating volume -- Monday, March 27, 4:30pm in Skiles 243
- March 30 --
Presentations: Random k-SAT: Atish and Danupon
- April 4 --
Presentations: Optimization on random instances: Yan and Nick
-
April 6 --
Presentations: Various: Fei and Joe
-
April 11 --
Presentations:
Random colorings: Gagan and Mitch
-
April 13 --
Presentations:
Chromatic number:
Charlie and Alex
- April 18 --
Presentations:
Coloring algorithms: Victor and Rishi
- April 20 -- Presentations:
Various: Bradley and Nipun
- Lecture 24 (Apr 25) --
Perfect Matchings in Random Bipartite Graphs
Email me as you decide on projects.
Below are some project ideas, but also just check out papers in
recent
FOCS,
STOC and
RANDOM conferences.
Or check the homepages of researchers in randomized algorithms. A few names:
Martin Dyer, Uri Feige, Alan Frieze, David Karger, Laci Lovasz, Alistair Sinclair, Santosh Vempala