The paper studies how well you can approximate the most important eigenvalue and eigenvector of a large random matrix using a specific class of algorithms. The algorithms work by repeatedly multiplying the matrix by a vector, which is essentially what the widely used "power iteration" method does. The key question is: how many steps, or equivalently, what polynomial degree, do you need before the approximation becomes accurate? The authors focus on two well-studied types of random matrices, one that is pure noise and one that has a hidden signal embedded in it.
For the signal-plus-noise case, called the spiked GOE, the paper identifies a sharp threshold on the polynomial degree needed to recover both the top eigenvalue and the leading eigenvector. This threshold depends on the signal strength in a precise logarithmic way, giving a much more exact answer than the conventional wisdom that roughly log(n) steps of power iteration suffice. For the pure noise case, called the GOE, recovering the top eigenvalue is surprisingly easy and requires only a constant number of steps, but recovering the corresponding eigenvector is much harder and requires around the cube root of the matrix dimension in degree. The authors also work out an exact formula for how good the approximation gets when you operate right at this threshold.
Beyond refining classical results in numerical linear algebra, the paper connects spectral methods, which are among the most commonly used tools in data science and machine learning, to a broader theoretical framework called low-degree polynomial algorithms. This framework is frequently used by researchers as a stand-in for understanding what can be done efficiently in polynomial time. The technical tools come from classical results about Chebyshev polynomials, which are optimal in a certain minimax sense, combined with deep results from random matrix theory about how eigenvalues of large random matrices behave.