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

Čas konání: Út. 9:00-10:30
Místo konání: S3, 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:

• Poznámky k přednášce, 2019.
• 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 5.11. 2019.
2. Do 3.12. 2019.
3. Do 7.1. 2020.