Lecture notes would be hopefully updated before (and probably
sometime after lecture). All notes in one
huge file.
Scribbles \& notes
- L01: Introduction
(1/16/24).
- L02: Some probability
notes,
01/18/24.
Probability, conditional probability, independence,
expectation, linearity of expectation, Markov's
inequality. Approximating \(k\)-SAT, distributed coloring.
- L03: Chebychev inequality
[pdf], 1/23/24.
- L04: Quick sort in
expectations,
Verification.
- L05: Occupancy. 1/30/24.
- L06: k-wide Independence.
2/1/24.
- L07: hashing.
2/6/24.
- L08: Closest pair,
Turán's theorem, and
derandomization via
conditional expectations (specifically,
3SAT).
2/8/24.
- L09:
Chernoff and
applications.
2/13/24.
- L10:
Discrepancy
and derandomization.
2/15/24.
- L11:
Routing on the hypercube.
Martingales.
2/20/24.
- L12:
Martingales 2.
2/22/24.
- L13:
Power of two choices.
2/27/24.
- L15:
Power of two choices part II.
2/29/24.
- L16:
Streaming
3/5/24.
- L17:
Frequency
estimation.
3/7/24
- L18:
Frequency
estimation 2.
3/19/24
- L19:
Random walk I
3/21/24
- L20:
Random walk II/
Random walk III
3/26/24.
- L21:
Random walk III
3/28/24.
- L22:
Random walk IV
4/2/24.
- L23:
Expanding graphs,
Random walk V,
Graph algebra,
4/11/24.
- L24:
Random walk continued.
4/13/24.
- L25:
Johnson-Lindenstrauss Lemma.
4/18/24.
- L26:
Entropy,
Entropy II,
- L27:
Shannon's theorem. 4/25/24.
- L28:
Min cut. 4/30/24.
Previous semester notes
A good starting point is lecture notes from previous semesters:
Last modified: Tue 2024-04-30 20:13:25 UTC 2024 by Sariel Har-Peled