Statistical Mechanics of Unsatisfiability and Glasses

Session

Glasses

25 May 2012, 09:00

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

263. Phase transition for cutting-plane approach to vertex-cover problem

Prof. Hartmann Alexander (University of Oldenburg)

25/05/2012, 09:00

We study the vertex-cover problem on Erdös-Reny random graphs, where previously a phase transition at connectivity c=e coinciding with an easy-hard transition of a branch- and-bound algorithm in connection with the leave-removal heuristic has been found. Hence, this algorithm works by partially exploring the space of feasible configurations. In this work, we consider an algorithm...

260. On existence of equilibrium domains in non-equilibrium systems

Dr Alexander Mozeika (Aalto University)

25/05/2012, 09:45

Equilibrium is a fundamental concept in statistical physics; it assumes that while the system dynamics is governed by microscopic interactions, some systems eventually reach a state where macroscopic observables remain unchanged. The evolution of many such systems is driven by the corresponding Hamiltonian energy function and their states converge to the equilibrium Gibbs-Boltzmann...

262. Analog approaches to hard optimization: from Sudoku to CNNs

Prof. Maria Magdolna Ercsey Ravasz (Babes-Bolyai University)

25/05/2012, 10:45

The analog dynamical system we recently designed to solve constraint satisfaction (Nature Physics 7, 966, 2011) opens potential new avenues to handle hard optimization problems. As an example I will present our Sudoku solver and show how it helps us define a type of "Richter scale" to characterize the hardness of Sudoku problems. These analog solvers are based on the...

251. Search methods for tile sets in patterned DNA self-assembly

Dr Eugen Czeizler (Aalto University)

25/05/2012, 11:30

We consider the problem of finding, for a given 2D pattern of coloured tiles, a minimal set of tiles assembling this pattern (in the abstract Tile Assembly Model of Winfree (1998)). This Patterned self-Assembly Tile set Synthesis (PATS) problem was first introduced by Ma and Lombardi (2008), and subsequently studied by Goos and Orponen (2010), who presented an exhaustive...

268. From sequence co-evolution to protein (complex) structure prediction

Prof. Martin Weigt (Université Pierre et Marie Curie)

25/05/2012, 14:00

Many families of homologous proteins show a remarkable degree of structural and functional conservation, despite their large variability in amino acid sequences. We have developed a statistical-mechanics inspired inference approach to link this variability (easy to observe) to structure (hard to obtain), i.e. to infer directly co-evolving residue pairs which turn our to form native...

266. Inference: an algebraic perspective

Prof. Matteo Marsili (Abdus Salam ICTP)

25/05/2012, 15:15

I will present a general framework which can be used to reconstruct probability distributions for strings of binary variables. While the problem of inference can be analytically controlled for small systems, a description of some of the regularization prescriptions needed to treat large systems will be provided, together with a discussion concerning their symmetries. Finally,...

265. Replica analysis of sparse l1-reconstruction with concatenated L-orthogonal basis

Dr Mikko Vehkaperä (KTH and Aalto University)

25/05/2012, 16:00

The sparse representation problem of recovering an N dimensional sparse vector x from M < N linear observations y = Dx given dictionary D is considered. The standard approach is to let the elements of the dictionary be independent and identically distributed (IID) zero-mean Gaussian and minimize the l1 norm of x under the constraint y = Dx. In this talk, we discuss the replica...