Phase Transitions, Backbones and Heuristic Search

A phase transition refers to such a phenomenon of a system (or combinatorial problem) in which some global properties change rapidly and dramatically when a control parameter crosses a critical value. A simple example of phase transition is water changing phases from solid (ice) to liquid (water) to gas (steam) as the temperature increases. The backbone of a problem is the fraction of variables that have fixed values among all solutions, which reflects the constrainedness of the problem. The concepts of phase transitions and backbones can be used to characterize typical-case properties of combinatorial problems. In this talk, I will give an overview of the research on understanding combinatorial optimization problems using phase transitions and backbones and on developing new heuristic search methods that exploit such intrinsic properties of difficult problems, including the Traveling Salesman Problem and Boolean satisfiability. I will emphasize my own contributions to these active research topics in the talk.