Thursday, February 9, 2006
<br>
4:15 P.M. to 5:15 P.M.
<br>
Packard 101<br>
<br>
<h2>Message-Passing Algorithms for Constraint Satisfaction Problems
</h2>
<b>Elitza Maneva<br>
UC Berkeley</b>
<br><br>
<b>Abstract:</b>
<br><br>
Over the last decade message-passing algorithms and graphical models
have found an increasing number of new applications. I will discuss such
algorithms in the context of constraint satisfaction problems (CSPs).
<br><br>
Belief propagation is a classical message-passing algorithm for
computing marginal distributions of a Markov random field. It is exact
only on tree graphs, but in many settings it is a good heuristic for
general graphs. I will introduce belief propagation with an example
application to the decoding of Fountain Codes. In the case of the
erasure channel, I will show an efficient procedure for computing the
success probability of the algorithm for finite-length codes.
<br><br>
Another message-passing algorithm that has recently attracted attention
with its ground-breaking performance is survey propagation. It is
designed for random CSPs, and in that setting it outperforms all other
algorithms known. It is motivated by modern approximation methods in
statistical physics, which are associated with the structure of the
solution space of typical problems. In my talk, I will demonstrate a
novel family of Markov random fields such that computing the marginal
distributions via belief propagation leads to a family of algorithms
generalizing survey propagation. This result highlights a general
combinatorial path towards designing message-passing algorithms that are
potentially more powerful than a naive application of belief
propagation.
<br><br>
Finally, I will describe some recent progress in our understanding of
the combinatorial properties of the solution space of constraint
satisfaction problems, as well as directions for future research.
<br><br>
<b> 
Short Biography:</b>
<br><br>
Elitza Maneva is a PhD candidate in the Electrical Engineering and
Computer Science Department at UC Berkeley with a designated emphasis on
Communication, Computation, and Statistics. She expects to graduate in
May 2006. She obtained her Bachelor's degree in Engineering and Applied
Science from the California Institute of Technology. During her studies
she has also done research at IBM Almaden, EPFL, and IBM T.J.Watson. Her
research interests are in the design and analysis of practical
algorithms for problems modeled by random structures. Her thesis work is
on belief propagation algorithms for random constraint satisfaction and
optimization problems, including random SAT and error-correcting
codes. She has also done research on sensor networks, game theory, and
quantum communication.