Home

Research and Publications

Curriculum Vitae

In general, I am interested in applications of probability theory, graph algorithms, statistics, and physics in the following areas:

- Distributed computation

- Optimization

- Network algorithms

- Machine learning and data mining

- Biomedical Informatics

- Coding theory.

In particular, I use message-passing algorithms and statistical physics techniques such as cavity method, in designing fast algorithms for large-scale computations.

2009

M. Bayati, R. Keshavan, A. Montanari, S. Oh, and A. Saberi, Generating random Tanner-graphs with large girth, Proceedings of IEEE Information Theory Workshop (ITW), 2009.

M. Bayati, J. H. Kim and  A. Saberi, A sequential algorithm for generating random graphs,
Algorithmica, Springer New York, July, 2009. ps , pdf.

M. Bayati, M.Gerritsen, D. Gleich, A. Saberi, and Y. Wang, Algorithms for Large, Sparse Network Alignment, To appear in Proceedings of IEEE International Conference on Data Mining (ICDM), 2009. pdf, Software and data.

M. Bayati, A. Montanari, and A. Saberi, Generating random graphs with large girth,

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009. ps , pdf.

M. Bayati, A. Braunstein and R. Zecchina, On the exactness of cavity method for the minimum spanning tree, Journal of Mathematical Physics (JMP) 2009. pdf.

M. Bayati, D. Gamarnik, and P. Tetali, Free energy limits in sparse random graphs, Preprint, 2009.

M. Bayati, M.Gerritsen, D. Gleich, A. Saberi, and Y. Wang, Matching Wikipedia Categories to the Library of Congress Subject Headings with Network Alignment, Preprint, 2009.

2008

M Bayati, C. Borgs, J. Chayes, R. Zecchina, On the exactness of the cavity method for weighted b-matchings on arbitrary graphs and its relation to linear programs, Journal of Statistical Physics (JSTAT), 2008. Longer version pdf.

M. Bayati, C. Borgs, A. Braunstein, J. Chayes, A. Ramezanpour, and R. Zecchina, Statistical Mechanics of Steiner Trees, Physical Review Letters (PRL) 2008. pdf.

M.Bayati, D. Shah and M. Sharma, Max-product for maximum weight matching: convergence, correctness and LP duality, IEEE Transactions on Information Theory, March 2008. ps , pdf.

2007

M. Bayati, J. H. Kim and  A. Saberi, A sequential algorithm for generating random graphs,
International workshop on Randomization and Computation (RANDOM), 2007.
Extended version is published in Algorithmica. ps , pdf.

M. Bayati, D. Gamarnik, D. Katz, C. Nair and P. Tetali, Simple deterministic approximation algorithms for counting matchings, ACM Symposium on Theory of Computing (STOC), 2007. ps , pdf.

M. Bayati, B. Prabhakar, D. Shah and M. Sharma, Iterative Scheduling Algorithms, IEEE Conference on Computer Communications (INFOCOM), 2007. ps , pdf.

2006

M. Bayati, Chandra Nair, A rigorous proof of the cavity method for counting matchings,
Allerton conference on communication, control and computing (ALLERTON), 2006. ps , pdf.

M. Bayati, M. Squillante and M. Sharma, Optimal scheduling in multi-server queuing network,
ACM SIGMETRICS/Performance, 2006. ps , pdf.

M. Bayati, D. Shah and M. Sharma, A simpler max-product maximum weight matching algorithm and the auction algorithm, IEEE International Symposium on Information Theory (ISIT), 2006. ps , pdf.

2005

N. Kumar, S. Nabar, M. Bayati, A. Keshavarzian, Achieving stability in networks of input queued switches using a local online scheduling policy, IEEE Global Communications Conference (GLOBECOM), 2005. pdf

M. Bayati, D. Shah and M. Sharma, Maximum weight matching via max-product belief propagation,
IEEE International Symposium on Information Theory (ISIT), 2005. ps , pdf

2004

M. Bayati, N. Beheshti, Stability of the maximum size matching in input queued switches,
Allerton conference on communication, control and computing (ALLERTON), 2004. ps , pdf

Working papers

M. Baily-Bechet, M. Bayati, C. Borgs, A. Braunstein, J. Chayes, and R. Zecchina, Building the yeast signalosome: a prize-collecting Steiner tree approach, Work in Progress.

Patents

M. Bayati, A. Braunstein, C. Borgs, J. Chayes and R. Zecchina, Network analysis with Steiner Trees, June 2008

M. Bayati, M. Braverman, S. Kale and Y. Makarychev, Predicting web-advertisement click success by using head-to-head ratings, January 2009.