TCS / Studies / T-79.300 Postgraduate Course in Theoretical Computer Science
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

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.)

Schedule (tentative)


  • 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.
[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 18 January 2005. Pekka Orponen.