Convex relaxations for certain inverse problems on graphs

Many maximum likelihood estimation problems are known to be intractable in the worst case. A common approach is to consider convex relaxations of the max-imum likelihood estimator (MLE), and relaxations based on semidefinite program-ming (SDP) are among the most popular. This thesis focuses on a certain class of graph-based inverse problems, referred to as synchronization-type problems. These are problems where the goal is to estimate a set of parameters from pairwise information between them. In this thesis, we investigate the performance of the SDP based approach for a range of problems of this type. While for many such problems, such as multi-reference alignment in signal processing, a precise explanation of their effectiveness remains a fascinating open problem, we rigorously establish a couple of remarkable phenomena. For example, in some instances (such as community detection under the stochas-tic block model) the solution to the SDP matches the ground truth parameters (i.e. achieves exact recovery) for information theoretically optimal regimes. This is estab