Before revision:  Consequentially, our algorithms achieve one-sided error: whenever they output that A is not PSD, they return a certificate that A has negative eigenvalues.
After revision:  Consequentially, our algorithms achieve one-sided error: whenever they output that A is not PSD, they return a certificate that \mathbf{A has negative eigenvalues.