Many perception and state estimation tasks in robotics and computer vision are naturally formalized as high-dimensional optimization problems that are known to be computationally hard (NP-hard) to solve in general; this class includes (for example) the fundamental problems of rotation averaging (in computer vision) and simultaneous localization and mapping (in robotics), among many others. Nevertheless, in this talk we present a class of certifiably correct estimation algorithms that are provably capable of efficiently recovering verifiably globally optimal solutions in many practical settings. Our approach is based upon convex relaxation: first, we develop convex (semidefinite) relaxations whose minimizers we prove provide exact, globally optimal solutions to the original estimation task for sufficiently small measurement noise; next, we describe specialized, structure-exploiting semidefinite optimization algorithms that enable even large-scale instances of these relaxations to be solved efficiently in practice. We illustrate the design of this class of methods on several fundamental 3D spatial estimation tasks (including rotation averaging, pose-graph optimization, and extrinsic camera calibration), demonstrating that our approach enables the recovery of globally optimal solutions to large-scale reconstruction problems involving tens to hundreds of thousands of variables in a matter of seconds.