|
|
Mohsen Bayati,
Stanford University
|
|
|
|
A Rigorous Analysis of the Cavity Method for Counting Matchings |
|
| Abstract |
Mr. Bayati will describe the use of the Cavity Method for counting the
number of matchings in a graph. In particular, he will describe how
Mezard and Zdeborova (2006) have applied this method to get an exact
count of the number of matchings. The Cavity Method is a very successful
heuristic from statistical physics and widely applicable to problems in
combinatorial optimization and coding theory. Its validity is
mostly supported by simulations and it is, therefore, important to
rigorize its use. In this talk, I will rigorously prove the validity of the cavity equations in the context of counting the number of matchings in large girth graphs. This is a joint work with Chandra Nair |
|
About the Speaker |
Mohsen Bayati
received a BSc degree in mathematics in 2000 from Sharif University of
Technology. He has also received an MS and PhD minor in mathematics from
Stanford University in 2003. Since then he has been working under the
supervision of Professors Balaji Prabhakar and Amin Saberi of Stanford
University towards his PhD in electrical engineering with expected
graduation in 2007. Mohsen Bayati was an intern with the stochastic analysis group at IBM research during summer 2005 and with the theory group at Microsoft research during summer 2006. He has been invited to be a post-doctoral researcher in the theory group at Microsoft research from 2007 to 2009.
|
|
