Factory Report: Statistical Mechanics of Unsatisfiability and Glasses, 23-26 May, 2012

Mariehamn has been recently developing into a focal point of Nordic science. The first Aalto Science Factory was held there to challenge computer scientists and physicists with the question: why are some problems difficult, indeed impossible to solve? The computer science research deals with such issues as if can one satisfy a large number of logical constraints with a small number of variables and a physicist looks at (spin) glasses as a paradigm. One central issue is when the structure of the energy landscape is crucial for the dynamical properties.

fact1pic1.jpg

Haijun Zhou and Silvio Franz discussing in a lively way glasses.

The workshop attracted a crowd of about 40 people from all over the world; 13 countries were represented. The first of the main scientific topics touched upon during the invited talks concerned challenges in inference (Bart Selman, Cornell) and how to look at satisfiability from the viewpoint of dynamical systems (Zoltan Toroczkai, Notre Dame), all on the ferry from Stockholm to Mariehamn. Next morning, Uriel Feige (Weizmann) told the audience how to actually show that a proposed formula is refutable (that is, not satisfiable). Tomi Janhunen (Aalto) then discussed Translated Answer-Set Programs and Elitza Maneva (Barcelona) graph (non-)isomorphisms. The day was finished by Dmitris Achlioptas (now Athens) on how to look at exhaustive attempts to solve problems of the SAT-type, and Stefan Szeider (Vienna) on the complexity of propositional satisfiability.

We continued on Friday by Alexander Hartmann (Oldenburg) who discussed the vertex cover problem as a physicist, and finished by Martin Weigt (Paris) on protein structure prediction (a hard bioinformatics, computer science, inference, AND physics problem) and Matteo Marsili (Trieste) on the theory of inference. The final Saturday had talks by Silvio Franz (Paris) on glass theory and computer science, by Haijun Zhou (CAS Beijing) on belief- and survey propagation for spin glasses, and by Toby Cubitt (Madrid) about showing that working out models for pretty much any systems is as in computer science NP-hard.

fact1pic2.jpg

Martin Weigt doing science in the appropriate way: animated and over a good dinner.

The first Aalto Science Factory was a success by all accounts, including the weather. The financial support of AScI was fundamental. The meeting was also supported heavily by the Nordic Institute for Theoretical Physics (NORDITA) based in Stockholm and represented by Ralf Eichhorn as an organizer. In this the Factory continues a tradition of some years of Nordita-Aalto meetings at Mariehamn and lays a base for future collaborations between NORDITA and AScI. The Factory was also supported by several graduate schools in Finland (FICS, HeCSE with Pekka Orponen as a co-organizer; NGSMP with Mikko Alava as an organizer) and KTH in Stockholm (Erik Aurell as an organizer).

fact1pic3.jpg

Science and early summer in Mariehamn (Alexander Hartmann, Uriel Feige).

Text: Mikko Alava
Photos: Pekka Orponen

Page content by: | Last updated: 12.03.2015.