## T-79.300 Postgraduate Course in Theoretical Computer Science (2-10 cr)## Autumn 2003
[Current]
[General Information]
[Schedule]
[Arrangements]
Previous years: [Spring 2003] [Autumn 2002] [Spring 2002] [Autumn 2001] [Spring 2001] Stochastic algorithms such as MCMC sampling, simulated annealing and genetic algorithms provide the currently perhaps most powerful general methodology for the approximate handling of computationally demanding tasks. While these techniques are being widely and succesfully applied to the solution of everyday practical problems, their theoretical foundations remain a fascinating, little-charted territory disclosing deep connections between computer science, mathematics, and theoretical physics. In the postgraduate TCS seminar this semester we shall take a concentrated look into some of the tools and analyses that have been applied to probe this area in recent years.
## Current- The seminar time has been moved to one hour earlier, i.e. 3-6 p.m.
- Complexity Transitions course first meeting Mon 15 Sep.
## General-
**Time, place:**Mondays, 3:15 thru 6:00 p.m., seminar room TB353. -
**Coordinator:**Pekka Orponen, room TB207. -
**Registration**by TOPI. -
**Prerequisites:**Basic knowledge of probability theory and stochastic processes (finite Markov chains); some familiarity with (combinatorial) optimisation problems and algorithms. The lecture notes of the course T-79.250 Combinatorial Models and Stochastic Algorithms provide useful background material. -
**Assets:**Familiarity with computational complexity theory, statistical mechanics. -
**Credits:**Seminar presentation plus archivable slides 2 cr per topic. Seminar paper plus 1 cr. Documented individual research additional 2 cr per topic. In addition, feedback must be provided for the speakers of at least five sessions using the respective electronic forms below. -
**Connections:**The seminar continues some of the themes of the course T-79.250 Combinatorial Models and Stochastic Algorithms and the Spring 2002 seminar on Combinatorial Landscapes. However attendance at neither of these is required as a prerequisite for participating in the present seminar. Concurrently with the seminar, a special course on Complexity Transitions in Optimisation Problems is being organised in collaboration with the Engineering Physics Department. The first few sessions of the seminar are arranged jointly with this special course, and on 17-19 October the course has an intensive weekend programme with lectures by some of the world's foremost experts. (For more details see the course link above.)
## Schedule (tentative)- 8 Sep: Opening, overview, handing out assigments (P.O.)
- 15 Sep: Opening of the
Complexity Transitions course.
Note different place Y228!
- 22 Sep: Optimisation in physics (Mikko Alava)
- 29 Sep: Algorithms and complexity (P.O.)
- 6 Oct: Phase transitions in optimisation (Mikko Alava)
- 13 Oct: Optimisation landscapes and heuristics (P.O.)
- 17-19 Oct: Complexity Transitions course weekend workshop at the Elohovi conference centre in Nuuksio. Speakers: Rémi Monasson, Alexander Hartmann. Updated program.
- 20 Oct: Ergodicity and convergence in Markov chains (Anne Patrikainen)
Suggested references: Brémaud (1999), Section 6.
Slides in pdf. Feedback form. - 27 Oct: Rapid mixing via conductance (Evimaria Terzi)
Suggested references: Sinclair (1993), Jerrum & Sinclair (1993), Jerrum (1998) Slides in pdf. Feedback form. - 3 Nov: Coupling methods (Teemu Hirsimäki)
Suggested references: Jerrum (1998) Slides in pdf. Feedback form. - 10 Nov: Exact sampling (Matti Järvisalo, Emilia Oikarinen)
Suggested references: Propp & Wilson (1996), Jerrum (1998), Wilson (2000), Häggström (2002), Sections 10-12 Slides in pdf (Järvisalo). Feedback form (Järvisalo). Slides in pdf (Oikarinen). Feedback form (Oikarinen). - 17 Nov: Markov chains on groups (Maarit Hietalahti)
Suggested references: Behrends (2000), Section 15 (and 16?), Diaconis (1988) Slides in pdf. Feedback form. - 24 Nov: Cancelled.
- 1 Dec: Dynamics of stochastic local search (Aapo Nummenmaa)
Suggested references: Barthel et al. (2003), Semerjian et al. (2003) Slides in pdf. Feedback form.
## Arrangements- Pointers to seminar material will be linked to the schedule above by coordinator.
- Electronic copy of presentation slides and/or seminar paper, together with any possible additional literature pointers mailed by presenter to coordinator by the presentation date. These will also be linked to the schedule above.
- Each speaker should discuss the material he/she intends to cover in his/her presentation with the coordinator ca. two weeks before the talk.
## Seminar material (to be completed)See also the list of material for the course T-79.250 Combinatorial Models and Stochastic Algorithms.- E. Aarts, J. K. Lenstra (eds.),
*Local Search in Combinatorial Optimization*. J. Wiley & Sons, Chichester, 1997. - W. Barthel, A. K. Hartmann, M. Weigt,
Solving satisfiability problems by fluctuations:
The dynamics of stochastic local search algorithms.
*Physical Review E 67*(2003), 066104. - E. Behrends,
*Introduction to Markov Chains, with Special Emphasis on Rapid Mixing*. Vieweg & Sohn, Braunschweig/Wiesbaden, 2000. - P. Brémaud,
*Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues*. Springer-Verlag, New York NY, 1999. - F. R. K. Chung,
*Spectral Graph Theory*. American Mathematical Society, Providence RI, 1997. - P. Diaconis,
*Group Representations in Probability and Statistics*. Institute of Mathematical Statistics, Hayward CA, 1988. - O. Häggström,
*Finite Markov Chains and Algorithmic Applications*. Cambridge University Press, 2002. - M. Jerrum,
"Mathematical foundations of the Markov chain Monte Carlo method."
In: M. Habib et al (eds.),
*Probabilistic Methods for Algebraic Discrete Mathematics*. Springer-Verlag, Berlin, 1998. (Manuscript version available here.) - M. Jerrum, A. Sinclair,
"Polynomial-time approximation algorithms for the Ising model."
*SIAM Journal on Computing 22*(1993), 1087-1116. (Manuscript version available here.) - M. Jerrum, A. Sinclair,
"The Markov chain Monte Carlo method: An approach to
approximate counting and integration."
In: D. Hochbaum (ed.),
*Approximation Algorithms for NP-Hard Problems*. PWS Publishing, Boston MA, 1997. (Manuscript version available here.) - M. Jerrum, A. Sinclair, E. Vigoda,
A polynomial-time approximation algorithm for the permanent
of a matrix with non-negative entries.
*Proc. 33rd ACM Symp. on Theory of Computing (STOC 2001)*, 712-721. - O. C. Martin, R. Monasson, R. Zecchina,
Statistical mechanics methods and phase transitions in
optimization problems.
*Theoretical Computer Science*265 (2001), 3-67. - M. E. J. Newman,
The structure and function of complex networks.
*SIAM Review 45*(2003), 167-256. - J. G. Propp, D. B. Wilson,
Exact sampling with coupled Markov chains and applications
to statistical mechanics.
*Random Structures and Algorithms 9*(1996), 223-252. (Manuscript version available here.) - C. M. Reidys, P. F. Stadler,
Combinatorial landscapes.
*SIAM Review 44*(2002), 3-54. - P. Salamon, P. Sibani, R. Frost,
*Facts, Conjectures, and Improvements for Simulated Annealing*. Soc. for Industrial & Applied Mathematics, Philadelphia PA, 2002. - G. Semerjian, R. Monasson,
Relaxation and metastability in a local search procedure
for the random satisfiability problem.
*Physical Review E 67*(2003), 066103. - A. Sinclair,
*Algorithms for Random Generation & Counting: A Markov Chain Approach*. Birkhäuser, Boston MA, 1993. - D. Wilson,
How to couple from the past using a read-once source of randomness.
*Random Structures and Algorithms 16*(2000), 85-113. - D. H. Wolpert, W. G. Macready,
No free lunch theorems for optimization.
*IEEE Transactions on Evolutionary Computation 1*(1997), 67-82.
[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links] Latest update: 18 January 2005. Pekka Orponen. |