Given a large random matrix A, we consider the following testing problem. Under the null hypothesis, every entry of A is generated i.i.d. from a distribution P_0. Under the alternative H_1, there is a submatrix indexed by Q, a subset of {1, 2, ... n} such that the entries of A in Q X Q are generated instead according to a different law P_1, while the other entries are as in the null. A special case of this problem is the hidden clique problem, which posits to find a clique in an otherwise random Erdos-Renyi graph. Although, information-theoretically, the testing problem is solvable via brute force search when |Q| = O(log n), no known polynomial time algorithm is known to even approach this threshold. I will discuss a powerful class of semidefinite programs, known as the Sum of Squares Hierarchy specialized to this problem, and establish computational lower bounds for the first level of the hierarchy that goes beyond vanilla spectral methods. The analysis involves controlling the eigenvalues of some non-standard ensembles of random matrices via the trace method. This is joint work with Andrea Montanari.