Technical Talk

(Click here for the slides of the talk.)
Title : Is SP BP?
Speaker : Prof. Yongyi Mao, University of Ottawa
When:Thursday, Nov. 8, 2007 from 1:30pm-2:30pm
Where:McMaster University, Room ITB/A113
Abstract : Survey Propagation (SP) is a recent celebrated algorithm in solving hard instances of constraint-satisfaction problems. Specifically, it has demonstrated its power in the classical NP-complete k-SAT problems and graph-coloring problems, as well as problems in communications and data compression. Heuristically passing messages on the factor-graph representations of the problem instances, SP shares many similarities with the well-known powerful algorithm in iterative decoding and statistical inference, namely, the Belief Propagation (BP) algorithm. Various recent efforts in understanding SP include the study of the connection between SP and BP, and in particular, whether SP is a special case of BP. To that end, some existing results have suggested that for the special case of k-SAT problems, SP and more generally its extension to a family of algorithms developed for k-SAT problems, which we call "weighted SP", may be regarded as instances of BP.

In this talk, I will present a general formulation of SP and weighted SP for arbitrary constraint-satisfaction problems, and in this most general context, answer the question "is SP BP?"

This talk is a joint work with Ronghui Tu and Jiying Zhao at the University of Ottawa.
Speaker Bio : Prof. Yongyi Mao received his Bachelor of Engineering degree at the Southeast University (Nanjing, China) in 1992. In 1995, he received his medical degree at Nanjing Medical University (Nanjing, China). In 1998, he obtained his Master of Science degree at the University of Toronto, in the Department of Medical Biophysics. In 2003, he completed his PhD in the Department of Electrical Engineering at the University of Toronto and joined the faculty of School of Information Technology and Engineering at the University of Ottawa as an Assistant Professor.

Prof. Mao's research interest spans areas of statistical inference, communications, data compressions, information theory and bioinformatics.