Mohsen Bayati's Publications

Journal Papers

M. Bayati, M. Lelarge and A. Montanari, Universality in Polytope Phase Transitions and Message Passing Algorithms, Submitted, 2012

M. Bayati, M. Braverman, M. Gillam, K. Mack, G. Ruiz, M. Smith, and E. Horvitz, Predictive Models and Policies for Minimizing Rehospitalizations for Congestive Heart Failure, Submitted, 2012

M. Bayati, C. Borgs, J. Chayes, Y. Kanoria, and A. Montanari, Bargaining dynamics in exchange networks, Submitted

M. Bayati, D. Gamarnik, and P. Tetali, Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, to appear in Annals of Probability, 2012

M Bayati, D. F. Gleich, A. Saberi, Y. Wang, Two message-passing algorithms for sparse network alignment, ACM Transactions of Knowledge Discovery and Data mining (TKDD), vol 7, pages 3:1-3-31, 2013
Software and Data

M. Bayati, and A. Montanari, The LASSO risk for gaussian matrices, IEEE Transcations on Information Theory, Vol. 58, No. 4, 2012

M. Bayati, and A. Montanari, The dynamics of message passing on dense graphs, with applications to compressed sensing, IEEE Transcations on Information Theory, Vol. 57, No. 2, 2011

M Bayati, C. Borgs, J. Chayes, R. Zecchina, Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions SIAM Journal in Discrete Math, 25, pp. 989-1011, 2011

M. Bayati, J. H. Kim and A. Saberi, A sequential algorithm for generating random graphs, Algorithmica, Vol. 58, No. 4, 2010
Software (by David Gleich)

M. Bayati, A. Braunstein, R. Zecchina, A rigorous analysis of the cavity equations for the minimum spanning tree, Journal. Math. Phys. 49, 125206,, 2009

M. Bayati, C. Borgs, A. Braunstein, J. Chayes, A. Ramezanpour, and R. Zecchina, Statistical Mechanics of Steiner Trees, Phys. Rev. Lett. (PRL) 101, 037208 ,, 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) L06001, 2008

M.Bayati, D. Shah and M. Sharma, Max-product for maximum weight matching: convergence, correctness and LP duality, IEEE Transactions on Information Theory, Vol. 54, No 3, 2008

Refereed Conference Papers

M. Bayati, M. Lelarge and A. Montanari, Universality in Polytope Phase Transitions and Iterative Algorithms ISIT 2012

Y. Kanoria, M. Bayati, C. Borgs, J. Chayes, and A. Montanari, Fast Convergence of Natural Bargaining Dynamics on Exchange Networks, ACM-SIAM Symposium on Discrete Algorithms, SODA 2011

Bayati, J. Bento and A. Montanari, The LASSO risk: asymptotic results and real world examples, NIPS 2010

M. Bayati, and A. Montanari, The dynamics of message passing on dense graphs, with applications to compressed sensing, ISIT 2010

M. Bayati, D. Gamarnik, and P. Tetali, Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, ACM Symposium on Theory of Computing, STOC 2010

M. Bayati, M.Gerritsen, D. Gleich, A. Saberi, and Y. Wang, Algorithms for Large, Sparse Network Alignment, Proceedings of IEEE International Conference on Data Mining, ICDM 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, A. Montanari, and A. Saberi, Generating random graphs with large girth, ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, Longer version
Information Theory Workshop version, ITW 2009
Software (by Raghu Keshavan and Sewoong Oh)

M. Bayati, J. H. Kim and A. Saberi, A sequential algorithm for generating random graphs, International workshop on Randomization and Computation, RANDOM 2007

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, Longer version

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

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

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

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

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

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

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

Patents

M. Bayati, M. Braverman, and E. Horvitz, Integrated system for healthcare analytics, decision support, alerts and experimentation, 2009

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

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