* the subgraph **G[A]* is highly structured in the sense that it is obtained from a small graph *H* (of order at most *C(p,ε)* by applying some blowup-like operations.

\end{compactitem}

We prove that classes of graphs which are nowhere dense (meaning that for every integer *p* there is a *p* subdivision of a finite complete graph that is isomorphic to no subgraph of a graph in *\mathcal C*) have the property that for every integer *p* and every *ε>0* every sufficiently large graph in the class has such an induced subgraph.

**Thursday, 11:00 - 11:25 h, Room: H 3004, Talk 2**

**Michael Chertkov**

Computing the permanent with belief propagation

**Coauthor: Adam B. Yedidia**

**Abstract:**

We discuss schemes for exact and approximate computations of permanents, and compare them with each other. Specifically, we analyze the Belief Propagation (BP) approach and its Fractional BP generalization to computing the permanent of a non-negative matrix. Known bounds and conjectures are verified in experiments, and some new theoretical relations, bounds and conjectures are proposed.

**Thursday, 11:30 - 11:55 h, Room: H 3004, Talk 3**

**Amin Coja-Oghlan**

Catching the k-NAESAT threshold

**Coauthor: Konstantinos Panagiotou**

**Abstract:**

The best current estimates of the thresholds for the existence of solutions in random CSPs mostly derive from the first and the second moment method. Yet apart from a very few exceptional cases these methods do not quite yield matching upper and lower bounds. Here we present an enhanced second moment method that allows us to narrow the gap to an additive *2*^{-(1-ok(1))k} in the random *k*-NAESAT problem, one of the standard benchmarks in the theory or random CSPs. This is joint work with Konstantinos Panagiotou.