  In the context of sparse principal component detection, we bring evidence
towards the existence of a statistical price to pay for computational
efficiency. We measure the performance of a test by the smallest signal
strength that it can detect and we propose a computationally efficient method
based on semidefinite programming. We also prove that the statistical
performance of this test cannot be strictly improved by any computationally
efficient method. Our results can be viewed as complexity theoretic lower
bounds conditionally on the assumptions that some instances of the planted
clique problem cannot be solved in randomized polynomial time.
