Most n-dimensional subspaces of R^m are Omega(√m)-far from the Boolean cube {-1, 1}^m (assuming n < cm for some constant c). Given a random n-dimensional subspace, how hard is it to certify that it is more than 𝛾√m-far from the cube? This question is relevant to the computational complexity of approximating the Sherrington-Kirkpatrick Hamiltonian, i.e. maximizing x^T A x over the Boolean cube for a matrix A sampled from the Gaussian Orthogonal Ensemble. The connection was discovered by Mohanty, Raghavendra, and Xu (STOC 2020). Improving on their work, Ghosh, Jeronimo, Jones, Potechin, and Rajendran (FOCS 2020) showed that certification is not possible in the sum-of-squares framework when m << n^1.5 even with 𝛾 = 0. I will present a non-deterministic interactive algorithm for this task when m >> n log n and 𝛾 << 1/mn^{1.5}. The algorithm is obtained by adapting a public-key encryption scheme of Ajtai and Dwork. The talk is based on joint work with Alon Rosen.