
T79.7003 Research Course in Theoretical Computer Science (6 cr) P V
Autumn 2007 (period I)
The topic of this special research course in Autumn 2007 is
Phase Transitions in Optimisation Problems.
The course is given by
Prof. Alexander
Hartmann from
the University of Oldenburg
(Germany).
Computational complexity deals with how fast a given problem can be
solved on a computer, dependend on the size of the problem. In
particular interesting are NPcomplete problems, where many everday
problems belong to. For these problems all known
algorithms exhibit a
running time, which increases in the worst case exponentially with the
problem size. On the other hand, despite heavy effort in the past
decades, there is no proof so far, that these problems cannot be solved
quickly, i.e. in polynomial time. This is the so called PNP problem,
for whose solution a price
of 1 Millon Dollars is dedicated by the Clay Institute of
Mathematics.
Since in real problems, one is often not confronted with the worstcase
but with typical problems, another approach to NPcomplete problems
is to study the typical behavior over ensembles
of random instances. This approach is similar to the way phase
transitions are studied in statistical physics. And indeed, for
some of the NPcomplete problems, recently phase transitions have been
observed, which, interestingly, coincide which drastical changes
of the typical computational complexity. Very often, the
hardesttosolve instances are found right at this phase boundary.
The new statistical physics approach to computational complexity
has helped to understand the behavior of NPcomplete systems better
and has led to the design of new efficient algorithms. Furthermore,
in some cases, analytical calculations of typical running times
have been performed. Hence, the activities at the interface of physics
and computer science might help to reach the ultimate goal, to
understand what makes a hard problem hard (if you believe in NP ≠
P).
This course gives an intruction to the new exciting field. Planned
outline of topics to be covered is:
 Introduction, TSP, spin glasses, phase transition in TSP
 Introduction to graphs, matchings
 Vertexcover problem
 Algorithms for the vertexcover problems: heuristics, branchandbound
algorithm, leafremoval algorithm, backbone algorithm, MonteCarlo
methods, parallel tempering approach
 Results for vertex cover on random graphs:
phase transition, running time
of algorithm, backbone, glassy phase, analytical results
 Solutionspace structure of vertexcover problems: direct clustering,
hierarchical clustering
 Physically/informationbased algorithms: warning propagation,
belief propagation, survey propagation
 Algorithms for the (K) satisfiability problem (KSAT):
simple 2SAT algorithm, linear 2SAT algorithm, DavisPutnam algorithm,
Walksat, restarts
 Results for 3SAT: phase transition, running time, analytical results
Blackboard notes
 Lecture 1, 11.9.2007
 Lecture 2, 12.9.2007
 Lecture 3, 25.9.2007
 Lecture 4, 27.9.2007
 Lecture 5, 2.10.2007
 Lecture 6, 4.10.2007
 Lecture 7, 9.10.2007
 Lecture 8, 11.10.2007
[Current]
[General]
[Lectures]
[Tutorials]
[Assignments]
[Exams]
[Course material]
[Literature]
Previous years: N/A
 [3 Aug 2007] No lectures on 18 and 20 September.
 [3 Aug 2007] First lecture
Tue 11 Sep 1214, room TB353,
and second lecture exceptionally
Wed 12 Sep 1214, room TB353.
 [4 Oct 2007] Presentation summaries (510 pages plain latex) must be
delivered by the 12 October 2007!
 [10 Oct 2007] Workshop program
available now.
 [18 Oct 2007] Course feedback form
will open on Monday 22nd.
 [18 Oct 2007] Course grades are now available.
 Lectures:
Prof. Alexander Hartmann
11 Sep  11 Oct , Tue & Thu 1214, room TB353.
Exceptions: second lecture on Wed 12 Sep,
no lectures on 18 & 20 Sep.
 Workshop:
The course concludes in a 1day workshop on Friday 12 Oct
10:0019:00
(room TB353), at which students present summaries of their
independent work on topics discussed at the course.
Details and location TBA.
The workshop program
is available now.
 Tutorials:
Fri 1012, room TB353. (Optional.)
 Examination: No examination; credit is based on
a workshop
paper & presentation (programming work possible on request).
Credits are also available to Physics students, for technical
details, please contact
Mikko Alava.
 Registration by
TOPI.
 Prerequisites: (C/C++) programming, basic knowledge
of algorithms and data structures, basics of computational complexity,
graph theory,
basics in statistical mechanics, presentation skills (using laptop,
MS power point or latexbased or similar)
Majoring in theoretical computer science of theoretical physics
Since this is an interdisciplinary course, many students may not
fulfull all prerequisites. Thus,
tutorial hours (Fridays) will
be used on request to give additional
lectures to teach missing foundations.
 Grading: Based on oral presantation AND short (510) page
summary of 13 selected scientific papers.
Tutorial hours (Fridays) will be used on request to give additional
lectures to teach missing foundations (see list above), to discuss
questions about the lecture and to discuss the material (scientific papers)
for the presentations.
Also facetoface tutorial lessons will be provided upon request to
discuss the scientific papers,
on which the presentations are based.
preparation of presentations
N/A
The course will follow the monograph:
 A. K. Hartmann, M. Weigt
Phase Transitions in Combinatorial Optimization Problems:
Basics, Algorithms and Statistical Mechanics
Wiley VCH (2005).
Overview/review papers:
The presentations are based on one of the following subjects:
Note 1: These publications are suggestions. If you find
scientific articles, which contain, to your opinion, better or
more interesting material on the given subject, the presentations
can also be based on those.
Note 2: Some papers may contain analytical calculations. For
preparing the
presentations, it is normally not necessary to follow all calculations
step by step. Also, help with the physics background will be provided
on request.
Note 3: Links to the published versions of the papers are given,
if available. Preprints of many papers can be found on
the preprint server arXiv. (some
links are included here, if no published version is available
electronically.)
 Phase transition in the
NumberPartitioning Problem (presented by Leena Salmela):
summary
 Modern WalkSAT algorithms (presented by Jari Rosti)
summary
 Calculation of phase boundary for the vertexcover problem (pure
analytical calculations)
 Chapters 7.3 and 7.4 in:
A. K. Hartmann, M. Weigt
Phase Transitions in Combinatorial Optimization Problems:
Basics, Algorithms and Statistical Mechanics.
Wiley VCH (2005).
 Martin Weigt and Alexander K. Hartmann
Minimal vertex covers on finiteconnectivity random
graphs  a hardsphere latticegas picture
Phys. Rev. E 63, 056127 (2001)

Calculation of typical running time of a branchandbound
algorithm for the vertexcover problem (some analytical
calculations necessary) (presented by Joni Pjarinen)
summary
 Chapter 8.1 in:
A. K. Hartmann, M. Weigt
Phase Transitions in Combinatorial Optimization Problems:
Basics, Algorithms and Statistical Mechanics.
Wiley VCH (2005).
 Martin Weigt and Alexander K. Hartmann
Typical Solution Time for a VertexCovering Algorithm on
FiniteConnectivity Random Graphs
Phys. Rev. Lett. 86, 1658 (2001)
 Calculation of typical running times of WalkSAT algorithms
(contains many analytical calculations)
 Chapter 10.3 in:
A. K. Hartmann, M. Weigt
Phase Transitions in Combinatorial Optimization Problems:
Basics, Algorithms and Statistical Mechanics.
Wiley VCH (2005).
 Wolfgang Barthel, Alexander K. Hartmann, and Martin Weigt
Solving satisfiability problems by fluctuations: The dynamics of
stochastic local search algorithms
Phys. Rev. E 67, 066104 (2003)
 Generating hard
but solvable SAT formulas
(presented by Andre Schumacher):
summary
 Phase transitions in generalized SAT problems
(presented by Juha Koivisto):
summary
 Phase transition in minimizing spinglass energies
(presented by Antti Hyvärinen>):
summary
 Vertexcover
problem (and variants) on other graph ensembles
(presented by Matti Peltomäkki):
summary

Phase transition in ground states of randomfield systems
and running time of maximumflow algorithmsy
(presented by Matti Sarjala)
summary
 Chapter 11.5 in:
A. K. Hartmann, M. Weigt
Phase Transitions in Combinatorial Optimization Problems:
Basics, Algorithms and Statistical Mechanics.
Wiley VCH (2005).
 Andrew V. Goldberg and Robert E. Tarjan
A new approach to the maximumflow problem
Journal of the ACM 35, 921 (1988)
 A. Alan Middleton
Critical Slowing Down in Polynomial Time Algorithms
Phys. Rev. Lett. 88, 017202 (2001)
 Combinatorial auctions
(presented by Olli Ahonen):
summary
 P. Cramton, Y. Shoham, and R. Steinberg
Combinatorial Auctions
MIT Press, (2006)
 Tobias Galla, Michele Leone, Matteo Marsili, Mauro
Sellitto, Martin Weigt, and Riccardo Zecchina
Statistical Mechanics of Combinatorial Auctions
Phys. Rev. Lett. 97, 128701 (2006)
 Unbiased generation of
metastable states for 2d Ising spin
glasses (presented by Petri Savola)
summary
 Report of summer project in 2006
 T.H. Cormen et al.
Introductions to algorithms
MIT Press (2001)
 C.H. Papadimitriou
Computational Complexity
AddisonWesley (1994)
 M.R. Garey and D.S. Johnson
Computers and intractability: a guide to the theory of
NPcompleteness
Freeman (1979)
 L. E. Reichl
A modern course in statistical physics
Wiley (1998)
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 27 February 2009.
Petri Savola
