Before revision:  B \|_F^2 = \sum_{i : \lambda_i(A) < 0 \lambda_i^2(A) } > \epsilon n^2  \succeq 0 denotes that \mathbf{B} is PSD} . Our main algorithmic contribution is a non-adaptive tester which distinguishes between these cases using only \tilde{O}(1/\epsilon^4) queries to the entries of A.
After revision:  B \|_F^2 = \sum_{i : \lambda_i(A) < 0 \lambda_i^2(A) } > \epsilon n^2 , where \mathbf{B \succeq 0 denotes that \mathbf{B} is PSD} . Our main algorithmic contribution is a non-adaptive tester which distinguishes between these cases using only \tilde{O}(1/\epsilon^4) queries to the entries of A.