NDMI025 - Pravděpodobnostní algoritmy - Randomized Algorithms

LS 2015 - Jiří Sgall
lectures: Monday 14:00 S4
recitations: Thursday 15:40 (March 12, April 2, April 16, and May 21)

Úkoly a cvičení - Homeworks and recitations

There will be four series of homework and four recitation sections for each of them. The dates for recitation sections are March 12, April 2, April 16, and May 21 (CHANGE!), the homework will be due before the lecture on Monday of the same week. For a pass grade (zápočet) you need 50% of the points (without bonus problems), every exercise is worth 2 points.

• Homework 1 (due March 9 before the lecture, recitation session is on March 12)
• Homework 2 (due March 30 before the lecture, recitation session is on April 2)
• Homework 3 (due April 13 before the lecture, recitation session is on April 16)
• Homework 4 (due May 18 before the lecture, recitation session is on May 21)

Výsledky

Probraná látka podle přednášek - Covered topics by lectures

• 1. (23. 2.)
• introductory examples: graph non-isomorphism, 3-colorable graphs - 2-coloring without monochromatic triangles
• definition of probabilistic complexity classes RP, BPP, PP, ZPP [MR 1.5]
• 2. (2. 3.)
• relations of probabilistic complexity classes to deterministic ones [MR 1.5, 2.3]
• Markov and Chebychev inequality [MU 3.1-3.3, MR 3.2]
• FastSelect - fast selection of median using sampling [MU 3.4, MR 3.3]
• 3. (9. 3.)
  
• Chernoff bounds [MU 4.2-4.3, MR 4.1] (see the summary)
  
• probability amplification
• permutation routing [MU 4.5.1, MR 4.2]
• 4. (16. 3.)
• random walks - introduction, hitting time, cover time
  
• random walks based algorithms for 2SAT and 3SAT [MU 7.1, MR 6.1]
• 5. (23. 3.)
• Markov chains, definitions, stationary distribution, its existence and convergence of the Markov chain to it [MU 7.2, MR 6.2]
• random walks on graphs [MU 7.4, MR 6.3]
• computation of hitting times and their relation to electrical networks [MR 6.4]
• 6. (30. 3.)
• bounds on hitting and cover times [MU 7.4, MR 6.5]
• connectivity, universal traversal sequences [MR 6.6]
• expanders and eigenvalues [MR 6.7]
• 7. (13. 4.)
  
• random walks on expanders [MR 6.8]
• Monte Carlo method for approximate counting [MU 10.1, MR 11.1]
• 8. (20. 4.)
  
• approximate counting of satisfying assignments for DNF [MU 10.2, MR 11.2]
• permanent - approximate counting of perfect matching using Markov chains [MU 10.2, MR 11.2]
• 9. (27. 4.)
  
• permanent - canonical paths
  
• coupling - introduction, shuffling, convergence speed [MU 11.1-11.2]
• coupling - approximate sampling of graph colorings [MU 11.4-11.5]
• 10. (4. 5.)
  
• bins and balls - basic bounds [MU 5.1-5.2.1]
  
• power of two choices - upper bound proof [MU 14.1]
  
• 11. (11. 5.)
• Yao-von-Neumann principle [MR 2.2]
  
• game tree evaluation - algorithm with expected time 3^k, lower bound 2.61^k [MR 2.1]
  
• 12. (18. 5.)
• PCP theorem - proof of the exponential version [MR 7.8, also http://iuuk.mff.cuni.cz/~sgall/pcp/]
• Bloom filters [MU 5.5.3]
  
• streaming - finding frequent elements [MU 13.4]
• 
  

Textbooks

[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 2013

Anotace

Přenáška o použití náhodnosti v algoritmech a protokolech. Náhodnost umožňuje řešit některé úlohy, které jsou bez jejího použití neřešitelné nebo řešitelné méně efektivně. Probereme základní techniky pro návrh a analýzu takových algoritmů a protokolů, ilustrované na konkrétních problémech. Předpokládá se znalost základních pojmů z teorie pravděpodobnosti (např. STP064) a teorie algoritmů (např. DMI026).

Osnova

• Příklady pravděpodobnostních algoritmů a protokolů. Třídy pravděpodobnostních algoritmů.
• Základní nerovnosti používané při analýze pravděpodobnostních algoritmů. Věty o minimaxu (von Neumann, Yao).
• Techniky pro omezení počtu náhodných bitů (po dvou nezávislé proměnné, expandery).
• Markovovy řetězce a náhodné procházky. Testování souvislosti grafů.
• Pravděpodobnostní algoritmy pro kombinatorické problémy.
• Hashování s konstantním časem vyhledávání.
• Pravděpodobnostní protokoly, kryptografie s veřejným klíčem (RSA, Rabinův systém).
• Náhodnost v on-line algoritmech.

Další informace

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