PhysDIS Workshop

Session

May 17

17 May 2008, 09:00

FB42 (<a href="http://www.albanova.se/">AlbaNova</a>)

271. On the approximability of Constraints Satisfaction Problems

Prof. Johan Håstad (KTH)

17/05/2008, 09:00

273. Computing the Tutte polynomial in vertex-exponential time

Dr Petteri Kaski (HIIT)

17/05/2008, 10:00

The deletion--contraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin--Kasteleyn in statistical physics. Prior to this...

274. Uniform sampling of local minima in Ising lattices

Prof. Pekka Orponen (TKK)

17/05/2008, 10:20

We present a combinatorial method for the uniform sampling of local energy minima in square and hexagonal 2D Ising spin glass lattices. The method has been used to estimate the number and energy distribution of local minima in lattices of up to 2000 spins.

272. Solution Counting for Combinatorial Problems: Exploiting BP, DPLL, and Statistics

Dr Ashish Sabharwal (Cornell)

17/05/2008, 11:00

We consider the problem of estimating the model count (number of solutions) of Boolean formulas, and present two techniques that compute estimates of these counts, as well as either lower or upper bounds with different trade-offs between efficiency, bound quality, and correctness guarantee. For lower bounds, we use a recent framework for probabilistic correctness guarantees, and exploit...

285. Clusters and solution landscapes for vertex-cover and SAT problems

Prof. Alexander Hartmann (University of Oldenburg)

17/05/2008, 13:00

277. Locked Constraint Satisfaction Problems

Lenka Zdeborova (U Paris-Sud)

17/05/2008, 14:00

We introduce the random `locked' constraint satisfaction problems. When increasing the density of constraints, they display a broad `clustered' phase in which the space of solutions is divided into many isolated points. While the phase diagram can be found easily, these problems, in their clustered phase, are extremely challenging from the algorithmic point of view: the best known...

278. Ark-less strategy for flood victims

Prof. Florent Krzakala (ESPCI, Paris)

17/05/2008, 14:20

In this talk, we will discuss (some) of the consequences of the phase transitions that arise in random constraint satisfaction problems, and present a simple strategy that allows to understand why it is so easy to find solutions in the clustered phase.

279. Learning to be lucky

Prof. Matteo Marsili (Abdus Salam ICTP)

17/05/2008, 15:00

280. Contact patterns of inpatients in a regional healthcare system

Dr Petter Holme (Coputational Biology)

17/05/2008, 16:00

In spite of advances in hospital treatment, hospitals continue to be a breeding ground for several airborne diseases and for diseases that are transmitted through close contacts like SARS, methicillin-resistant Staphylococcus aureus (MRSA), norovirus infections and tuberculosis (TB). Here we extract contact networks for up to 295,108 inpatients for durations up to two years from...

281. The (many) phase transitions in random constraint satisfaction problems

Prof. Federico Ricci-Tersenghi (Roma)

17/05/2008, 16:20

282. The Jarzynski identity: lessons from the Random Energy model

Prof. Matteo Palassini (Barcelona)

17/05/2008, 16:40