In this thesis we consider computational problems related to many-body spin systems with a structured energy operator, a local Hamiltonian. We begin with the most structured setting where the Hamiltonian has a spectral gap and spatial locality. This setting is widely studied using approximate ground space projectors (AGSPs). In chapter 1 we give an improved analysis of AGSPs in the setting of local Hamiltonians with a degenerate ground space. This implies a direct generalization of the AGSP⇒entanglement bound implication of [Arad, Landau, and Vazirani ’12] from unique to degenerate ground states. We use the improved analysis to give a particularly simple algorithm for frustration-free spin systems provided an AGSP with structure as a matrix product operator. We apply our tools to a recent 2D area law of [Anshu, Arad, and Gosset ’21], giving a sub-exponential-time classical algorithm to compute the ground states. This time complexity cannot be improved beyond sub-exponential assuming the randomized exponential time hypothesis, even for the special case of classical constraint satisfaction problems on the 2D grid. In chapter 2 we consider frustrated systems and extend results for spin chains to certain trees with intrinsic dimension β < 2. This condition is met for generic trees in the plane and for certain models of hyperbranched polymers in 3D. In chapter 3 we relax the conditions on the Hamiltonian and no longer require a spectral gap or geometric locality, and we consider an approximation problem for the spectrum of the local Hamiltonian. We give a simple proof of a Chernoff bound for the spectrum of a k-local Hamiltonian based on Weyl’s inequalities. The complexity of estimating the spectrum’s ϵ(n)-th quantile up to constant relative error thus exhibits the following dichotomy: For ϵ(n) = d −n the problem is NP-hard and maybe even QMA-hard, yet there exists constant a > 1 such that the problem is trivial for ϵ(n) = a −n.Ph.D.