Polynomial Precision Dependence Solutions to Alignment Research Center Matrix Completion Problems

The motivation for these problems is to enable efficient computation of heuristic estimators to formally evaluate and reason about different quantities of deep neural networks in the interest of AI alignment [3]. Our solutions involve reframing the matrix completion problems as a semidefinite program (SDP) and using recent advances in spectral bundle methods for fast, efficient, and scalable SDP solving. Proving that this task is at least as hard as dense matrix multiplication or positive semidefinite testing would count as a resolution. Question 2 (fast "approximate squaring"): Given A R The core idea is to formulate both questions as semidefinite programs (SDP) and use a spectral bundle method [1, 5, 9-11] to implicitly solve the SDP or obtain a certificate of infeasibility. In the case where the SDP is infeasible, our method computes an upper bound quantifying the degree to which the SDP is infeasible.