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. |