Saturday, last workshop day - May 17th

Last night, social activities interfered with science as we had a very nice workshop dinner at Restaurant Godthem in Djurgården.

Today instead, the last day was celebrated (during an otherwise rainy day) with a lot of program. The audience reached again 40-45 at maximum (the early morning being an exception). The first part was on computer science/physics -related issues, with three long contributions. First Johan Håstad told us why (eg.) MAX-SAT is so very difficult to approximate (actually you can as well try a random assignment...). Then, Ashish Sabharwal and Alexander Hartmann educated the audience more on why Constraint Satisfaction Problems (CSP) are interesting. Ashish talked about how to sample the number of solutions cleverly, and Alex about analyzing clustering in COL and 3-SAT and its relation to what Local Search does. The structure of the CSP solution (and energy) landscape was also addressed in short talks by Frederico Ricci-Tersenghi, Florent Krzakala, and Lenka Zdeborova.
They all presented very recent results.

Finally, the Saturday was finished with some mixed topic -talks, and with Matteo Marsili discussing How to Be Lucky, or how to park (in Marseille).

Hopefully all participants liked this event, in particular those who came to Stockholm/Nordita only for the workshop and not also for the program.

Monday 5th at Nordita

Today the program started. And it did it so via an opening talk by Erik Aurell. He explained the background of SMDIS and its funny relation to the sister program at KITPC, Beijing. Together these account for three months of science that at the end may help to define what is this "SMDIS". Erik went through a number of issues discussed in China to explain to the non-experts some of the challenges that a physicist faces in particular in Constraint Satisfaction Problems (3-SAT is a keyword), like what to say about the UNSAT-phase. Then, the constraint density is so high that an instance of the (say) 3-SAT problem can not be solved, it has a "positive energy" in that the optimal assignment leaves some constraints violated. It is a challenge to find physics-based approaches to beat the computer science techniques for proving unsolvability.

Finally, Erik listed some (pet) directions that really deal with "SMDIS" or at least contain the DIS-part and look for statistical mechanics for new ideas - or did so already. Examples arise in distributed Peer-to-Peer systems, in overlay network management (dynamics), and in designing distributed algorithms for evolving, complex networks.

Tomorrow we shall have a first real talk (sorry Erik) by Luca Peliti (Naples), then on Wednesday Olav Tirkkonen (TKK, Helsinki).