Vybrané kapitoly z výpočetní složitosti I

Čas konání: Středa 9:00 (první přednáška 11.10.2017)
Místo konání: S1, Malá Strana

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován expanderům a náhodným procházkám na grafech. Expandery jsou grafy s velkou souvislostí, jejichž užití nalezneme jak ve výpočetní složitosti (například při zmenšování chyby pravděpodobnostních algoritmů), tak při konstrukci samoopravných kódů. Náhodné procházky na grafech mají mnoho aplikací: počínaje konstrukcí nejrůznějších algoritmů pro testování souvislosti grafů (paralelně, v malém prostoru...) a konče PageRankem firmy Google.

Přednáška je určena především studentům vyšších ročníků studia a doktorandům. Přednáška předpokládá základní znalosti z výpočetní složitosti, pravděpodobnosti a diskrétní matematiky. Přednášku je možné si zapsat opakovaně.

Plán přednášky

• Expandery, jejich existence.
• Explicitní konstrukce: Margulis, zig-zag součin.
• Zmenšování chyby pravděpodobnostních algoritmů.
• Superkoncentrátory a jejich použití
• Samoopravné kódy vycházející z expanderů.
• Deterministický algoritmus pro testování souvislosti grafu v logaritmickém prostoru (Reingold 2004).
• Markovův proces, stacionární distribuce.
• Náhodná procházka na grafu, očekávaná doba pokrytí. 
• Mixing time.
• Pravděpodobnostní algoritmus pro testování souvislosti grafu v logaritmickém prostoru (Aleliunas et al.1980).

Literatura:

• Akualizované poznámky k přednášce.
• Shlomo Hoory, Nati Linial and Avi Wigderson. Expander Graphs and their Applications. 2003. Lecture notes.
• Dieter van Melkebeek. Expander Graphs and Applications. 2006. Lecture notes.
• László Lovász. Random Walks on Graphs: A Survey.
• David Aldous and James Allen Fill. Reversible Markov Chains and Random Walks on Graphs.

Shrnutí pravděpodobnosti.

Domácí úkoly

1. Do 1.11. 2017.
2. Do 29.11. 2017.
3. Do 10.1. 2018.

Zkouška