0368.4622
Seminar on random walks on graphs
Fall 2009.
Lecturer: Amnon TaShma
When and where: Mondays, 11:1013:00. Location Shenkar 114.
Grading: Based on participation in class and paper presentation.
Olle Häggström 

Lecture Notes. Counting, sampling and integrating: algorithms and complexity 

Russ Bubley 
Randomized Algorithms: Approximation, Generation and Counting 
Notes on counting 
A
polynomialtime approximation algorithm for the permanent of a matrix
with nonnegative entries.
M.
Jerrum, A. Sinclair, and E. Vigoda
In
Journal
of the ACM, 51(4):671697, 2004.
A preliminary version appears
in STOC
2001.
Fulkerson
prize, 2006.
Download: PDF
V. Guruswami Rapidly Mixing Markov Chains: A Comparison of Techniques
O. Reingold, Undirected STConnectivity in LogSpace, STOC 2005.
Dorit Aharonov Class on Markov Chains in Theoretical Computer Science
Date 
Speaker 
Topic 
Reference 
(1) 19.10.09

אמנון תאשמע 
Introduction. Basic definitions. Simple examples. Overview of seminar. 

(2) 26.10.09

אמנון תאשמע 
Markov chains. The Markov chain convergence theorem (with a coupling proof). The coupling lemma. A random walk on the cube. 
[HAG, 45][Freeze, 2.3] 
() 2.11.09 
לא התקיים שיעור בגלל עץ שנפל על מסילת הרכבת 


(3) 9.11.09 
מילה גנדלסמן 
Sampling . Gibbs sampler. The hardcore model. Random qcoloring in degree d graphs. Fast convergence of the Gibbs sampler, q>2d^2 
[HAG, 68], [Jerrum Chapter 4 ] 
(4) 16.11.09

עומר 
Path coupling. Fast convergence of the Gibbs sampler, q>2d+1. Linear extension of a partial order. PPTI PPTII 
[Freeze 2.4] [Jerrum Chapter 4 ] [Bubley, Inyrtmezzo: Path coupling],[Bubley, 5.7] 
(5) 23.11.09 
דני לשם 
Sampling the Ising model exactly, using the PropWilson algorithm 
[HAG, 1011] 
() 30.11.09 



(6) 7.12.09 
שי ורדי 
Exact counting. #P (Facts) Approximate counting qcol in BPP General Approximate counting in BPP^NP 
[Jerrum Chapter 2 ] [HAG, 9][Jerrum Chapter 3 ] [Gold, 6.2.2.2] 
(8) 14.12.09 (9) 21.12.09 (10) 28.12.09 
אילן בןבסט עמרי 
Bounding mixing time through spectral gap, conductance, path congestion.  undirected graph  Reversible MC  general directed graphs. II 
[Freeze, 2.1,2.2,2.3] 
(11) 4.1.10 
רועי כגן 
Sampling and approximate counting for weighted matchings (the monomerdimer model) 
[Freeze, 3.1,3.2] 
(12) 11.1.10 
דני לב 
Counting perfect matchings in bipartite graph. Permanent of matrices with nonnegative values. The overall structure. Thm 3.3.2 
[Freeze, 3.3] [Jerrum Chapter 5 ] 
(13) 18.1.10 
רועי ורנר 
Reingold's algorithm for undirected connectivity in Logspace 







