Title: Deterministic approximation algorithms for counting matchings

Speaker:  Chandra Nair
Information Engineering, CUHK 


Date: Friday, April 11, 2008
Time 11:00-12:00PM
Venue: Room 3501, HKUST

 Abstract: We develop an FPTAS for counting matchings in bounded degree 
graphs, a #P-complete problem. This work is directly motivated by the 
work of Mezard et. al. - spin glass physicists - who used "Cavity 
method" to derive heuristics for counting matchings in graphs. We 
rigorize this work for classes of graphs to yield deterministic 
approximation algorithms.


References:
Simple deterministic approximation algorithms for counting matchings/
M. Bayati, D. Gamarnik, D. Katz, C. Nair, and P. Tetali.
Proceedings of the Symposium on Theory of Computation (STOC), pp. 
122-127, 2007.

A rigorous proof of the cavity method for counting matchings,
M. Bayati and C. Nair.
| Proceedings of the 44th Annual Allerton Conference on Communication, 
Control and Computing,2006. |