## ANR Project GAP

Graphs, Algorithms and Probability

Back to the the project page

M. Lelarge. Loopy annealing belief propagation for vertex cover and matching: convergence, LP relaxation, correctness and Bethe approximation.
M. Leconte, M. Lelarge, L. Massoulié. Adaptive Replication in Distributed Content Delivery Networks.
C. Bordenave, A. Sen, B. Virag. Mean quantum percolation.
E. Coupechoux, M. Lelarge. Contagions in Random Networks with Overlapping Communities.
M. Bayati, M. Lelarge, A. Montanari. Universality in Polytope Phase
Transitions and Message Passing Algorithms. to appear in Annals of Applied Probability.
H. Amini, M. Lelarge. The
Diameter of Weighted Random Graphs. under revision for Annals of Applied Probability.
E. Coupechoux, M. Lelarge. How Clustering Affects Epidemics in Random Networks. to appear in Advances in Applied Probability.

2014
J. Xu, L. Massoulié, M. Lelarge. Edge Label Inference in Generalized Stochastic Block Model: From Spectral Theory to Impossibility Results. COLT 2014.

2013
M. Lelarge, H. Zhou.
Sublinear-Time Algorithms for Monomer-Dimer
Systems on Bounded Degree Graphs. ISAAC 2013.
T. Bonald, A. Proutiere. Two-Target Algorithms for Infinite-Armed Bandits with Bernoulli Rewards. NIPS 2013.
M. Lelarge, A. Proutiere, S. Talebi. Spectrum Bandit Optimization. ITW 2013.
M. Lelarge, L. Massoulié, J. Xu. Reconstruction in the Labeled Stochastic Block Model. ITW 2013.
M. Lelarge. Bypassing
Correlation Decay for Matchings with an Application to XORSAT. ITW 2013.
M. Leconte, M. Lelarge, L. Massoulié. Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing. SODA 2013:35-46.
C. Bordenave, M. Lelarge and J. Salez. Matchings on infinite graphs. Probability Theory and Related Fields, 157(1-2):183-208, 2013.
H. Amini, M. Draief, M. Lelarge. Flooding in Weighted Sparse
Random Graphs. SIAM Journal on Discrete Mathematics, 27(1):1-26, 2013.

2012
M. Lelarge.
Coordination in Network Security Games: a Monotone Comparative Statics
Approach. IEEE JSAC 30(11):2210-2219, 2012.
M. Lelarge. Diffusion and Cascading Behavior in Random Networks. Games Econ. Behav., 75(2):752-775, 2012.
M. Lelarge. A new approach to the
orientation of random hypergraphs. SODA 2012:251-264.
M. Leconte, M. Lelarge and L. Massoulié.
Bipartite graph structures for efficient balancing of heterogeneous
loads. SIGMETRICS 2012:41-52.