Organizers: Mikko Alava (HUT/Physics) and Pekka Orponen (HUT/Computer Science)
 

This course concentrates on the statistics of hard optimization problems,  as exemplified
by the travelling salesman problem. Recent progress, both in algorithms and in the theory,
have highlighted both WHY and HOW these are difficult to treat. In particular, tools have
been loaned from Statistical Physics. (See, e.g. Nature 400, 133; Science 297, 812)

The greatest recent successes have been with respect to the satisfiability problems (of
logical clauses) which due to the equivalence of the NP-complete class of complexity
creates exciting prospects. The purpose of this course is to introduce the participants
to the phenomenology of complexity in optimization, and to recent research for both
Algorithms and Theoretical treatments, using ideas from the physics of spin glasses.

We intend the course to be of interest both to CS and physics students, with the
necessary background covered for both in the material.

The course will be organized with introductory lectures, to be held at HUT weekly
during the first half of the fall semester (15.9 and onwards), and with an Intensive
Course at the HUT conference center at Sjokulla, 30 kms from the campus, October
17-19th. To pass, attendance, an oral exam concerning the material, (and for further
credits a home project) is needed (3-6 HUT credits/study weeks, ECTS: multiply by 2).

NOTE: Sjokulla has been replaced by "Elohovi", a hotel
close to the Nuuksio natural part. (25.9 situation). The
schedule remains the same. See www.elohovi.com

The external lectureres for the course are Remy Monasson (ENS, Paris), a world-class
expert on the physics of disordered systems, and Bart Selman (Cornell, USA), who
will represent the computer science viewpoint. Also, local people (HUT, at least)
contribute with guest lectures. As an application, Alexander Hartmann (Gottingen, Germany)
will discuss the vertex cover problem.

Funding for the participants (Intensive Course) is provided by HUT (HUT students) and by the
National Graduate School for Materials Physics (physics graduate students). Others, please
sign up and contact the organizers, by September 15th at the latest.

Accommodation is provided at Sjokulla for upto about 25 people. For students who
might not be covered by the funding organized, the cost of full-board is about 40 Euros
per night.

Program of the course (13.8. version):

Lectures (Y228, main building):

Monday 15.9, Introduction, 15.00. 22.9, 29.9, 6.10 and 13.10: 15-18
(MA: 22.9 and 6.10, PO: 29.9 and 13.10).

NEW: lecture notes (or postscript versions of transparencies)

Monday 15.9: Orponen: basics
Monday 15.9: Alava: why is this interesting?
Monday 22.9:  Alava: basic statistical physics for optimization
Monday 29.9: Orponen: Turing machines, complexity classes...
Monday 6.10: Alava: basic  constraint counting for optimization
Monday 13.10: Orponen: approximate algorithms, search landscapes

Problems about the statistical mechanics part: part 1 now available!
These will be discussed on Monday 6.10.
Problems about the CS part: now available!

If you have not received any email from the organizers please send your email address
(assuming you are a  participant...) to Mikko Alava

Elohovi-program:

FRIDAY 17.10:

9.30 -10. 30 ARRIVAL (transport to be decided and agreed) to SJOKULLA,
10.30 Selman,  12.00 Lunch,  13.30 Monasson, 15.00 Coffee, 15.30 Hartmann,
17.00 Dinner, 18.30 Sauna and general social program.

SATURDAY 18.10:

9.00 Monasson, 10.30 Coffee, 11.00 Selman, 12.30 Lunch, 14.00 Monasson,
15.30 Coffee, 16.00 local contributions, 17.00 Dinner, 18.30 as on Friday...

SUNDAY 19.10:

9.00 Monasson, 10.30 Coffee, 11.00 Selman, 12.30 RETURN to HUT/Helsinki
(details: see Friday)
 
 

Mikko Alava and Pekka Orponen ----------------->Here!