Title: Phase Transitions in Optimization Problems, and Algorithmic Implications
Speaker: Gregory Sorkin, IBM Research
Date: October 5, 2006 Time: 11:25 am - 12:05 pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Phase transitions in random structures are an essential feature of statistical physics, play an important role in discrete mathematics, and have algorithmic implications. Some of the most interesting questions center around random 3-Sat (the satisfiability of randomly generated Conjunctive Normal Form formulas with 3 literals per clause), but because this is so hard to analyze, we often instead prove results for constraint satisfaction problems with clauses of length 2. For example, it is known that random 3-Sat undergoes a phase transition from almost-sure satisfiability to almost-sure unsatisfiability as the "clause density" increases, but it is not known exactly where this transition occurs, or even that the transition point tends to a constant. By contrast, the transition of random 2-Sat at density 1 is already a classical result, and more recently the transition's "scaling window" has been comprehensively analyzed. While 2-Sat is an easy decision problem, its optimization equivalent, Max 2-Sat, is NP-hard, and undergoes a similar phase transition, with the same scaling window. On the algorithmic side, it is known that sparse instances of random 3-Sat can, with high probability, be satisfied by efficient algorithms, but it is not known if this persists right up to the phase transition point. For "semi-random" 2-variable constraint satisfaction problems (a class encompassing random Max 2-Sat and random Max Cut), an algorithm running in expected linear time optimally solves instances of density up to the giant-component threshold, and indeed through the scaling window.
see: DIMACS 2006-2008 Special Focus on Discrete Random Systems