Rutgers Discrete Mathematics Seminar

Title: Thresholds for inverse problems on random graphs

Speaker: Emmanuel Abbe, Princeton University

Date: Tuesday, April 15, 2014 2:00pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ


We consider inverse problems on random graphs, where vertex-variables are to be recovered from dependent edge-variables. In particular, we consider the linear inverse problem Y=I(G)X+Z, where I(G) is the incidence matrix of an Erdos-Rényi random graph, X is the vector of vertex-variables assumed to be Boolean, and Z is an iid noise vector. In the absence of noise, X can be fully recovered if and only if G is connected, with a sharp threshold at log(n)/n, and X can be partially recovered (more than 50%) if and only if G has a giant component, with a sharp threshold at 1/n. We will show how these thresholds are rescaled in order to cope with the noise. Concentration results and recovery algorithms will be discussed. Based on joint works with A. Bandeira, A. Bracher, A. Singer, and A. Montanari.