Statistical Mechanics of Unsatisfiability and Glasses

Session

Ferry session

23 May 2012, 16:45

Ferry Stockholm-Mariehamn and Hotel Arkipelag, Mariehamn, Åland

267. New Challenges in Inference Technology

Prof. Bart Selman (Cornell University)

23/05/2012, 17:00

In recent years, we have seen tremendous progress in inference technologies. For example, in the area of Boolean satisfiability (SAT) and Mixed Integer Programming (MIP) solvers now enable us to tackle significant practical problem instances from applications in hardware and software verification, planning, and scheduling. Key to this success is the ability to strike the right...

257. An Analog Approach to Boolean Satisfiability

Prof. Zoltan Toroczkai (University of Notre Dame)

23/05/2012, 18:00

Boolean satisfiability (k-SAT) is one of the most studied optimization problems, as an efficient (polynomial-time) solution to k-SAT (for k > 2) implies efficient solutions to a very large number of hard optimization problems. Here we propose a mapping of k-SAT into a deterministic continuous-time dynamical system with a unique correspondence between its attractors and the k-SAT...