Spring 2010
[Main Page] [Assignments]
I will post lecture topics as we go along.
Topics |
Date(s) |
Reading |
Relevant complexity classes Fingerprinting I: |
Tuesday January 12
|
[Mot-Rag] Chapters 1.5 and 7.1 - 7.2
Also relevant is [Mitz-Upfal] Chapters 1.1-1.3 |
Fingerprinting II:
|
Thursday January 14
|
[Mot-Rag] Chapters 7.3 - 7.6
|
Karger's Min-Cut Algorithm
|
Tuesday January 19
|
Lecture Notes(PDF)
See also: |
Randomized median finding in linear time
|
Thursday January 21
|
[Mitz-Upfal] Chapter 3.4
[Mot-Rag] Chapter 3.3 |
Chernoff Bounds
|
Tuesday January 26
|
[Mitz-Upfal] Chapter 4.1-4.2
[Mot-Rag] Chapter 4.1 |
Balls into bins: Power of 2 choices
|
Tuesday February 2
|
[Mitz-Upfal] Chapter 14.1 |
Probabilistic Method: Max-cut
|
Thursday February 4
|
[Mitz-Upfal] Chapters 6.2-6.3 |
Probabilistic Method: Max-SAT
|
Tuesday February 9
|
[Mot-Rag] Chapter 5.2 |
Probabilistic Method: Property B
|
Thursday February 11
|
Lecture notes |
FPRAS for #DNF
|
Tuesday February 16
|
[Mot-Rag] Chapters 11.1-11.2
[Mitz-Upfal] Chapters 10.1-10.2 |
FPRAS for Network Unreliability
|
Thursday February 18
|
Lecture Notes
|
FPRAS for #Knapsack
|
Tuesday February 23
|
Lecture Notes
|
Pairwise independent random variables
Derandomization of approximation |
Thursday February 25
|
[Mitz-Upfal] Chapter 13.1
|
2-Universal Family of Hash Functions
Perfect Hashing |
Tuesday March 2
|
[Mitz-Upfal] Chapter 13.3
|
Bloom Filters |
Thursday March 4
|
[Mitz-Upfal] Chapter 5.5
|
Parallel Algorithm for Maximal Independent Set |
Tuesday March 9
to Thursday March 11 |
Lecture Notes(PDF)
See also: |
Parallel Algorithm for Constructing a
Perfect Matching, if one exists |
Tuesday March 16
|
[Motwani-Raghavan]
Chapter 12.4
|
Approximate counting via approximate sampling |
Tuesday March 30
|
Lecture notes from my MCMC course
See also: |
Markov Chain Fundamentals |
Thursday April 1
|
Lecture notes from my MCMC course
See also: |
Coupling applications |
Tuesday April 6
|
[Mitz-Upfal] Chapter 11 |
Relationship between mixing time and:
|
Thursday April 8
|
|
Applications of canonical paths technique
Generating a random matching |
Tuesday April 13
|
|
Estimating the permanent |
Thursday April 15
|
|
Estimating the volume of a convex body |
Tuesday April 20
|
|
Project presentations
Schedule - see here |
Thursday April 22 to
Tuesday May 4 |