NDMI025 - Pravděpodobnostní algoritmy - Randomized Algorithms

Spring/LS 2021 - Jiří Sgall - Friday 10:40

Covered topics

• 1. (March 5)
• 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. (March 12)
• 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, universal traversal sequences [MR 6.6]
• 3. (March 19)
• 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 26)
  
• permutation routing [MU 4.5.1, MR 4.2]
• expanders and eigenvalues [MR 6.7]
• 5. (April 9)
  
• random walks on expanders [MR 6.8]
• 6. (April 16)
  
• 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. (April 23)
• permanent - approximate counting of perfect matching using Markov chains [MU 10.2, MR 11.2]
• permanent - canonical paths
• 8. (April 30)
• coupling - introduction, shuffling, convergence speed [MU 11.1-11.2]
• coupling - approximate sampling of graph colorings [MU 11.4-11.5]
• 9. (May 7)
• 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]
• 10. (May 14)
• streaming - counting distinct items [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 2 and 3]
• 11. (May 21)
• streaming - counting distinct items
• streaming - sketches, finding frequent items [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 5]
• 12. (May 28)
• streaming - frequency moments [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, Ch. 6 and 7]
• PCP theorem, intro
  
• 13. (June 4)
• PCP theorem - proof of the weak version, linearity testing [MR 7.8, http://iuuk.mff.cuni.cz/~sgall/pcp/]

Učebnice

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

Předchozí běh přednášky v LS 2019

Další informace

Přednáška se nekoná každý rok, předpokládám její opakování za 2 roky.