Colloquium - 01.06.2017
|Title||The Phase Transition in Heuristic Search|
|Speaker||Prof. J. Christopher Beck (University of Toronto)|
|Time||Thursday 1 June 2017, from 17:15 - 18:15 o'clock|
|Location||Department of Mathematics and Computer Science, Seminar Room 00.003, University of Basel, Spiegelgasse 1, Basel|
The Phase Transition in Heuristic Search
In the mid-1990s, it was observed, over many problem classes such as SAT and CSP, that the likelihood that a randomly generated problem instance has a solution transitions quickly from almost definitely one to almost definitely zero over a narrow range of a problem generation parameter. Furthermore, the observed computational difficulty peaked during this transition at a point where approximately half of the generated problems had a solution. This phenomenon has come to be known as the phase transition with the most popular example being seen in parameter of the clause-to-variable ratio of random SAT problems. Much empirical and theoretical work ensued with one result in the constraint programming community being an acknowledgement that numeric experiments should take into account the phase transition when generating suites of test problems for algorithm comparison.
Bio: J. Christopher Beck is a Professor in the Department of Mechanical & Industrial Engineering at the University of Toronto. Chris' MSc and PhD degrees both come from the Department of Computer Science, University of Toronto, in the area of Artificial Intelligence. His research interests include scheduling, constraint programming, hybrid optimization techniques, mixed integer programming, AI planning, reasoning under uncertainty, and queueing theory. He has published over 100 papers in international journals and conferences in these areas.