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).
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment