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

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

Home assignments

Exams

Course material

• A. K. Hartmann, M. Weigt
  Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics
  Wiley VCH (2005).

• B. Hayes
  Can't get no satisfaction
  American Scientist 85, 108 (1997)
• S. Mertens
  Computational Complexity for Physicists
  Computing in Science & Engineering 4(3), 31 (2002)
• B. Hayes
  On the Threshold
  American Scientist 91, 12 (2003)

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
   • S. Mertens
     Phase Transition in the Number Partitioning Problem
     Phys. Rev. Lett. 81, 4281 (1998)
   • S. Mertens
     A complete anytime algorithm for balanced number partitioning
     preprint arxiv.org/abs/cs.DS/9903011 (1999)
   • S. Mertens
     The Easiest Hard Problem: Number Partitioning (Review)
     in: A.G. Percus, G. Istrate and C. Moore, eds., Computational Complexity and Statistical Physics
     Oxford University Press (2006), p. 125-139
     see also: preprint arxiv.org/abs/cond-mat/0310317
2. Modern Walk-SAT algorithms (presented by Jari Rosti) summary
   • Sakari Seitz, Mikko Alava and Pekka Orponen
     Focused local search for random 3-satisfiability
     J. Stat. Mech. P06006 (2006) (not available at TKK) see also: preprint arxiv.org/abs/cond-mat/0501707
   • John Ardelius and Erik Aurell
     Behavior of heuristics on large and hard satisfiability problems
     Phys. Rev. E 74, 037702 (2006)
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
   • W. Barthel, A. K. Hartmann, M. Leone, F. Ricci-Tersenghi, M. Weigt, and R. Zecchina
     Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach
     Phys. Rev. Lett. 88, 188701 (2002)
   • H.X. Jia, C. Moore, and B. Selman
     From spin glasses to hard satisfiable formulas
     LECTURE NOTES IN COMPUTER SCIENCE 3542, 199 (2005)
7. Phase transitions in generalized SAT problems (presented by Juha Koivisto): summary
   • James M. Crawford and Larry D. Auton
     Experimental results on the crossover point in random 3-SAT
     Artificial Intelligence 81, 31 (1996) (doi:10.1016/0004-3702(95)00046-1)
   see also homepage of J.M. Crawford
   • Allen Van Gelder
     Autarky Pruning in Propositional Model Elimination Reduces Failure Redundancy
     Journal of Automated Reasoning 23, 137(1999) (doi:10.1023/A:1006143621319)
   • Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky
     2+p-SAT: Relation of typical-case complexity to the nature of the phase transition
     Random Structures and Algorithms 15, 414 (1999)
8. Phase transition in minimizing spin-glass energies (presented by Antti Hyvärinen>): summary
   • Frauke Liers, Michael Jünger, Gerhard Reinelt, Giovanni Rinaldi
     "Computing Exact Ground States of Hard Ising Spin Glass Problems by Branch-and-Cut
     New Optimization Algorithms in Physics" (edited by Alexander Hartmann and Heiko Rieger), 47 (2004)
   • Frauke Liers, Matteo Palassini, Alexander K. Hartmann, and Michael Jünger
     Ground state of the Bethe lattice spin glass and running time of an exact optimization algorithm
     Phys. Rev. B 68, 094406 (2003)
9. Vertex-cover problem (and variants) on other graph ensembles (presented by Matti Peltomäkki): summary
   • Alexei Vázquez and Martin Weigt
     Computational complexity arising from degree correlations in networks
     Phys. Rev. E 67, 027101 (2003)
   • Pablo Echenique, Jesús Gómez-Gardeñes, Yamir Moreno, and Alexei Vázquez
     Distance-d covering problems in scale-free networks with degree correlations
     Phys. Rev. E 71, 035102(R) (2005)
   • C. W. Fay, IV, J. W. Liu, and P. M. Duxbury
     Maximum independent set on diluted triangular lattices
     Phys. Rev. E 73, 056112 (2006)
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