Tutorials

In September, there will be one more exam on Sept 18. If you need
a different date during the summer, it may be possible - write me
a mail.

- 1. (Feb 13)
- introductory examples: graph non-isomorphism, 3-colorable graphs - 2-coloring without monochromatic triangles
- Markov chains, definitions, stationary distribution, its existence and convergence of the Markov chain to it [MU 7.2, MR 6.2, notes on stationary distribution]
- 2. (Feb 20)
- random walks on graphs [MU 7.4, MR 6.3]
- computation of hitting times and their relation to electrical networks [MR 6.4]
- bounds on hitting and cover times [MU 7.4, MR 6.5]
- connectivity[MR 6.6]
- 3. (Feb 27)
- universal traversal sequences [MR 6.6]
- definition of probabilistic complexity classes RP, BPP, PP, ZPP [MR 1.5]
- relations of probabilistic complexity classes to deterministic ones [MR 1.5, 2.3]
- Chernoff bounds [MU 4.2-4.3, MR 4.1] (see the summary)

- probability amplification
- 4. (March 6)

- permutation routing [MU 4.5.1, MR 4.2]
- expanders and eigenvalues [MR 6.7]
- 5. (March 13) and further plan
- expanders and eigenvalues [MR 6.7]
- random walks on expanders [MR 6.8]
- 6. (March 20)

- Monte Carlo method for approximate counting [MU 10.1, MR 11.1]
- approximate counting of satisfying assignments for DNF [MU 10.2, MR 11.2]
- 7. (March 27)
- permanent - approximate counting of perfect matching using Markov chains [MU 10.2, MR 11.2]
- permanent - canonical paths
- 8. (April 3)
- coupling - introduction, shuffling, convergence speed [MU 11.1-11.2]
- coupling - approximate sampling of graph colorings [MU 11.4-11.5]
- 9. (April 17)
- streaming - counting distinct items, tidemark algorithm, median trick [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 2]
- 10. (April 24)
- streaming - counting distinct items, BJKST algorithm [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 3]
- streaming - approximate counting, Morris counter, median-of-means trick [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 4]
- 11. (April 25)
- streaming - sketches, finding frequent items, count-sketch [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 5]
- streaming - frequency moments [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 6 and 7]
- 12. (May 15)
- Yao-von-Neumann principle [MR 2.1]

- game tree evaluation - algorithm with expected time 3
^{k}, lower bound 2.61^{k}[MR 2.2, M. Tarsi: Optimal Search on Some Game Trees. J. ACM 30(3): 389-396 (1983), also Tarsi-GameTrees.pdf here] - PCP theorem, intro
- 13. (May 22)
- PCP theorem - proof of the weak version, linearity testing [MR 7.8, http://iuuk.mff.cuni.cz/~sgall/pcp/]

[MR] R. Motwani, P. Raghavan: Randomized algorithms.

[MU] M. Mitzenmacher, E. Upfal: Probability and Computing:
Randomized Algorithms and Probabilistic Analysis