The Rotations Averaging Problem (as it is known in Computer Vision) is to infer an orientation for each node in a graph, given measurements of relative orientation on the edges of the graph. Here an orientation is a 3D rotation (i.e., an element of the special orthogonal group SO(3)). In the computer vision application, the vertices represent cameras in a scene, and edges exist where cameras see common scene elements. Rotations averaging is a manifold-valued optimization problem. We would like to be able to solve it under intrinsic cost functions, such as the L1 or L2 geodesic costs, but these problems are nonlinear and known to have false local minima. In this talk, I will describe ongoing work to characterize the local minima of the L1 and L2 geodesic formulations. I will show an empirical mapping of the cost surface and give a result (for the L2 case only) pertaining to how problem instance structure affects a notion problem instance difficulty. The result hinges on quotient-manifold understanding of a fundamental symmetry in the problem. I will also mention the approaches we are taking as we try to extend the analysis to the L1 case. This project is joint work between myself and David Bindel.