New for: D1
In this talk, I will present a graphical model that captures the complexity of PPZ on a broad class of instances. Focusing on upper bounds, I will present three probabilistic approaches, drawing ideas from statistical physics and information theory. The last approach yields a tight upper bound of 2^{-n + cn \log k/k} on these instances, for some constant c>0. This is joint work with my thesis advisor Dominik Scheder.