EECS500 Fall 2011 Department Seminar

Harold Connamacher
The Satisfiability Threshold of Random Problems
Case School of Engineering
White Bldg., Room 411
11:30am - 12:30pm
September 27, 2011


A group of researchers attempting to classify the average difficulty of some notoriously hard problems (such as the NP-complete problems) made an interesting discovery.  For many problems, if you consider random instances with an increasing number of constraints, the probability that the instance has a solution undergoes a sudden transition at a specific constraint density. This threshold in the probability of having a solution attracted the attention of physicists and mathematicians because it seems similar to other thresholds in physical and mathematical structures such as thresholds encountered in random graphs and the transitions in an iron magnet as it cools.  Despite over a decade of work on the subject, the major questions are still unresolved.  This talk will survey the subject and describe some recent results.


Harold Connamacher is an Assistant Professor in the Department of Electrical Engineering and Computer Science at Case Western Reserve University.

Connamacher earned a B.A. from Oberlin College in 1991, a M.S. from the University of Oregon in 2000, and a Ph.D. from the University of Toronto in 2008.    From 1992 to 1997, he worked as a software engineer at an image processing start-up company in Buffalo, New York. From 1997 to 2000 he was a senior software engineer at Automated Securities Clearance of Weehawken, New Jersey, a stock market company now part of SunGard Data Systems.  From 2004 to 2005, he was a programmer and project manager at the Data Management Group in the Joint Program in Transportation at the University of Toronto.  From 2005 to 2011, Dr. Connamacher was an assistant professor of computer science at Albion College, in Albion, Michigan.

Connamacher's research interests are in graph theory, algorithms, and constraint satisfaction problems.