NDMI025 - Pravděpodobnostní algoritmy - Randomized Algorithms

Spring/LS 2023 - Jiří Sgall - Mon 14:00 (2pm) S4

Exams

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.

Covered topics

• 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/]

Textbooks

[MR] R. Motwani, P. Raghavan: Randomized algorithms.
[MU] M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Previous run, Fall (LS) 2021