|
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.
- The seminar time has been moved to one hour earlier,
i.e. 3-6 p.m.
-
Complexity Transitions course first meeting Mon 15 Sep.
- 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.)
- 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.
- 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.
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.
|