Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica (ex-Scienze dell'Informazione) - D(S)I
via Salaria 113, piano terzo
Aula Seminari

Abstract:
Message passing expectation maximization algorithms on factor graphs are at the heart of many proposed approaches to managing resources and distributed functions on the global Internet. Although I have just committed at least 8 buzzwords in the preceding sentence, these really are a consistent pattern seen in successful local algorithms for solving problems on unlimited scale when communications costs are comparable to computing effort. Work in applying spin glass methods to problems in combinatorics done in recent years by Mezard, Monasson, Parisi, Zecchina and their colleagues offer the best avenue for understanding why and how these methods can be successful and where they will need extension. I'll talk about some work in progress exploring different ways of deriving message passing formulations of K-SAT and the "belief propagation" analyses that permit solving these problems on very large scales by making existing algorithms smarter.