0368.4622
Seminar on random walks on graphs
Fall 2009.
Lecturer: Amnon Ta-Shma
When and where: Mondays, 11:10-13: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
polynomial-time approximation algorithm for the permanent of a matrix
with non-negative entries.
M.
Jerrum, A. Sinclair, and E. Vigoda
In
Journal
of the ACM, 51(4):671-697, 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 ST-Connectivity in Log-Space, 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, 4-5][Freeze, 2.3] |
|
(-) 2.11.09 |
לא התקיים שיעור בגלל עץ שנפל על מסילת הרכבת |
|
|
|
(3) 9.11.09 |
מילה גנדלסמן |
Sampling . Gibbs sampler. The hard-core model. Random q-coloring in degree d graphs. Fast convergence of the Gibbs sampler, q>2d^2 |
[HAG, 6-8], [Jerrum Chapter 4 ] |
|
(4) 16.11.09
|
עומר |
Path coupling. Fast convergence of the Gibbs sampler, q>2d+1. Linear extension of a partial order. PPT-I PPT-II |
[Freeze 2.4] [Jerrum Chapter 4 ] [Bubley, Inyrtmezzo: Path coupling],[Bubley, 5.7] |
|
(5) 23.11.09 |
דני לשם |
Sampling the Ising model exactly, using the Prop-Wilson algorithm |
[HAG, 10-11] |
|
(-) 30.11.09 |
|
|
|
|
(6) 7.12.09 |
שי ורדי |
Exact counting. #P (Facts) Approximate counting q-col 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 monomer-dimer model) |
[Freeze, 3.1,3.2] |
|
(12) 11.1.10 |
דני לב |
Counting perfect matchings in bipartite graph. Permanent of matrices with non-negative 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 |
|
|
|
|
|
|
|
|
|
|