NDMI025 - Pravděpodobnostní algoritmy - Randomized Algorithms

Spring/LS 2025 - Jiří Sgall - Tue 14:00 (2pm) S6

Covered topics

• 1. (Feb 18)
• introductory examples: graph non-isomorphism, 3-colorable graphs - 2-coloring without monochromatic triangles
• Markov chains, definitions, stationary distribution
• 2. (Feb 25)
• Markov chains, stationary distribution, its existence and convergence of the Markov chain to it [MU 7.2, MR 6.2, notes on stationary distribution]
• 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]
• 3. (March 4)
• connectivity [MR 6.6]
• 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]
• 4. (March 11)
  
• Chernoff bounds [MU 4.2-4.3, MR 4.1] (see the summary)
  
• probability amplification
• permutation routing [MU 4.5.1, MR 4.2] - introduction
  
• 5. (March 18)
• 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]
• 6. (March 25)
  
• permutation routing [MU 4.5.1, MR 4.2]
• expanders and eigenvalues [MR 6.7]
• 7. (April 1)
  
• expanders and eigenvalues [MR 6.7]
• random walks on expanders [MR 6.8]
• intro, rapid mixing
• 8. (April 8)
  
• random walks on expanders [MR 6.8]
• proof of derandomization
  
• 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]
• 9. (April 15)
• permanent - approximate counting of perfect matching using Markov chains [MU 10.2, MR 11.2]
• permanent - canonical paths
• 10. (April 22)
• streaming - counting distinct items, tidemark algorithm, median trick [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 2]
• 11. (April 29)
• streaming - counting distinct items, BJKST algorithm [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 3]
• streaming - sketches, finding frequent items, count-sketch [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 5]
• 12. (May 6)
• streaming - approximate counting, Morris counter, median-of-means trick [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 4]
• streaming - frequency moments [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 6 and 7]
• 13. (May 20)
• 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) 2023