  Compressed sensing is a technique for finding sparse solutions to
underdetermined linear systems. This technique relies on properties of the
sensing matrix such as the restricted isometry property. Sensing matrices that
satisfy the restricted isometry property with optimal parameters are mainly
obtained via probabilistic arguments. Given any matrix, deciding whether it
satisfies the restricted isometry property is a non-trivial computational
problem. In this paper, we give reductions from dense subgraph problems to the
certification of the restricted isometry property. This gives evidence that
certifying the restricted isometry property is unlikely to be feasible in
polynomial-time. Moreover, on the positive side we propose an improvement on
the brute-force enumeration algorithm for checking the restricted isometry
property.
  Another contribution of independent interest is a spectral algorithm for
certifying that a random graph does not contain any dense k-subgraph. This
"skewed spectral algorithm" performs better than the basic spectral algorithm
in a certain range of parameters.
