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

T-79.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 NP-complete 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 P-NP 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 worst-case but with typical problems, another approach to NP-complete 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 NP-complete problems, recently phase transitions have been observed, which, interestingly, coincide which drastical changes of the typical computational complexity. Very often, the hardest-to-solve instances are found right at this phase boundary.
The new statistical physics approach to computational complexity has helped to understand the behavior of NP-complete 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:

  1. Introduction, TSP, spin glasses, phase transition in TSP
  2. Introduction to graphs, matchings
  3. Vertex-cover problem
  4. Algorithms for the vertex-cover problems: heuristics, branch-and-bound algorithm, leaf-removal algorithm, backbone algorithm, Monte-Carlo methods, parallel tempering approach
  5. Results for vertex cover on random graphs: phase transition, running time of algorithm, backbone, glassy phase, analytical results
  6. Solution-space structure of vertex-cover problems: direct clustering, hierarchical clustering
  7. Physically/information-based algorithms: warning propagation, belief propagation, survey propagation
  8. Algorithms for the (K-) satisfiability problem (K-SAT): simple 2-SAT algorithm, linear 2-SAT algorithm, Davis-Putnam algorithm, Walksat, restarts
  9. Results for 3-SAT: phase transition, running time, analytical results
Blackboard notes
  1. Lecture 1, 11.9.2007
  2. Lecture 2, 12.9.2007
  3. Lecture 3, 25.9.2007
  4. Lecture 4, 27.9.2007
  5. Lecture 5, 2.10.2007
  6. Lecture 6, 4.10.2007
  7. Lecture 7, 9.10.2007
  8. Lecture 8, 11.10.2007


[Current] [General] [Lectures] [Tutorials] [Assignments] [Exams] [Course material] [Literature]

Previous years: N/A


Current

  • [3 Aug 2007] No lectures on 18 and 20 September.
  • [3 Aug 2007] First lecture Tue 11 Sep 12-14, room TB353, and second lecture exceptionally Wed 12 Sep 12-14, room TB353.
  • [4 Oct 2007] Presentation summaries (5-10 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.


General

  • Lectures: Prof. Alexander Hartmann 11 Sep - 11 Oct , Tue & Thu 12-14, room TB353. Exceptions: second lecture on Wed 12 Sep, no lectures on 18 & 20 Sep.
  • Workshop: The course concludes in a 1-day workshop on Friday 12 Oct 10:00-19: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 10-12, 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 latex-based 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 (5-10) page summary of 1-3 selected scientific papers.

Tutorial problems

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 face-to-face tutorial lessons will be provided upon request to discuss the scientific papers, on which the presentations are based.

Home assignments

preparation of presentations

Exams

N/A

Course material

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

  1. Phase transition in the Number-Partitioning Problem (presented by Leena Salmela): summary
  2. Modern Walk-SAT algorithms (presented by Jari Rosti) summary
  3. Calculation of phase boundary for the vertex-cover 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 finite-connectivity random graphs -- a hard-sphere lattice-gas picture
      Phys. Rev. E 63, 056127 (2001)
  4. Calculation of typical running time of a branch-and-bound algorithm for the vertex-cover 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 Vertex-Covering Algorithm on Finite-Connectivity Random Graphs
      Phys. Rev. Lett. 86, 1658 (2001)
  5. 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)
  6. Generating hard but solvable SAT formulas (presented by Andre Schumacher): summary
  7. Phase transitions in generalized SAT problems (presented by Juha Koivisto): summary
  8. Phase transition in minimizing spin-glass energies (presented by Antti Hyvärinen>): summary
  9. Vertex-cover problem (and variants) on other graph ensembles (presented by Matti Peltomäkki): summary
  10. Phase transition in ground states of random-field systems and running time of maximum-flow 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 maximum-flow problem
      Journal of the ACM 35, 921 (1988)
    • A. Alan Middleton
      Critical Slowing Down in Polynomial Time Algorithms
      Phys. Rev. Lett. 88, 017202 (2001)
  11. 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)
  12. Unbiased generation of metastable states for 2d Ising spin glasses (presented by Petri Savola) summary
    • Report of summer project in 2006

General literature

  • T.H. Cormen et al.
    Introductions to algorithms
    MIT Press (2001)
  • C.H. Papadimitriou
    Computational Complexity
    Addison-Wesley (1994)
  • M.R. Garey and D.S. Johnson
    Computers and intractability: a guide to the theory of NP-completeness
    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