We study the structure of the set of algebraic curvature operators satisfying a sectional curvature bound under the light of the emerging field of convex algebraic geometry. More precisely, we determine in which dimensions n this convex semialgebraic set is a spectrahedron or a spectrahedral shadow; in particular, for n ≥ 5, these give new counterexamples to the Helton-Nie conjecture. Moreover, efficient algorithms are provided if n = 4 to test membership in such a set. For n ≥ 5, algorithms using semidefinite programming are obtained from hierarchies of inner approximations by spectrahedral shadows and outer relaxations by spectrahedra.