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

Michal Koucký
<koucky@iuuk.mff.cuni.cz>

LS 2015/2016

TIN086 - 2/1 Z, Zk

První přednáška se koná v pondělí 29.2.2016 v 9:00 v S10

Čas konání: Pátek 9:00-10:30 (kromě první přednášky, která je v pondělí 29.2. místo 4.3.)
Místo konání: S10 - 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. Náhodné procházky na grafech mají fascinující vlastnosti, souvisí s mnoha jinými obory jako například s toky v elektrických sítích a mají nesčetně aplikací: počínaje konstrukcí nejrůznějších algoritmů pro testování souvislosti grafů (paralelně, v malém prostoru...), přes clustering až po PageRank 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

• Markovův proces
• Stacionární distribuce, konvergence k ní
• Náhodná procházka na grafu
• Očekávaná doba první návštěvy a pokrytí
• Expanze grafu a mixing time
• Krátké náhodné procházky
• Náhodné procházky na dynamických grafech
• (Elektrický) odpor grafů
• Deterministické náhodné procházky
• Užití: PageRank, individuální PageRank, clustering

Literatura:

• Aktualizované poznámky.
• James R. Norris. Markov Chains, Cambridge University Press, 1998.
• Olle Häggström. Finite Markov Chains and Algorithmic Applications, Cambridge University Press, 2002.
• László Lovász. Random Walks on Graphs: A Survey.
• David Aldous and James Allen Fill. Reversible Markov Chains and Random Walks on Graphs.
• Peter G. Doyle. J. Laurie Snell. Random walks and electric networks.
  
  
• Greg Barnes and Uriel Feige. Short random walks on graphs. SIAM J. Discrete Math. 9(1): 19-28 (1996).
• Satoshi Ikeda, Izumi Kubo, Norihiro Okumoto, and Masafumi Yamashita. Impact of local topological information on random walks on finite graphs. ICALP 2003.
• Chen Avin, Michal Koucký, and Zvi Lotker. How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). ICALP 2008.
  
  
• Prasad Tetali. Random Walks and the Effective Resistance of Networks. Journal of Theoretical Probability 4 (1991), 101-109.
• Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The Electrical Resistance of a Graph Captures its Commute and Cover Times. Computational Complexity, 6(4): 312-340 (1997).
  
  
• Reid Andersen, Fan Chung, and Kevin Lang. Using pagerank vectors to locally partition a graph. Internet Math. 4(1):35-64 (2007).

Domácí úkoly

1. Do 29.3. 2016.
2. Do 15.4. 2016.