Modern applications in statistics, machine learning and computer science routinely involve combinatorial optimization problems. These problems can be intractable when the input size is large. Convex relaxations are commonly employed in this scenario. Semidefinite programs are natural powerful algorithms in this class. They are particularly well suited when the input is in matrix or graph form. In...