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

Michal Koucký
<koucky@math.cas.cz>

ZS 2008/2009

TIN085 - 2/1 Z, Zk

Čas konání: Středa 12:20
Místo konání: 3 patro, chodba nad KAMem, Malá Strana

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován náhodným procházkám na grafech a expanderům. 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. 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ů.

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

• 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).
• Expandery, jejich existence.
• Explicitní konstrukce: Margulis, zig-zag součin.
• Zmenšování chyby pravděpodobnostních algoritmů.
• Samoopravné kódy vycházející z expanderů.
• Deterministický algoritmus pro testování souvislosti grafu v logaritmickém prostoru (Reingold 2004).

Literatura:

• László Lovász. Random Walks on Graphs: A Survey.
• David Aldous and James Allen Fill. Reversible Markov Chains and Random Walks on Graphs.
• 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.

Shrnutí pravděpodobnosti.

Domácí úkoly

1. Do 29.10. 2008.
2. Do 19.11. 2008.
3. Do 9.1. 2009.