Matrices that satisfy Restricted Isometry Property (RIP) are well studied and used in compressed sensing. One such class of matrices, important in practice, can be obtained by randomly sampling rows of a Discrete Fourier Transform matrix. It is not known, and considered notoriously challenging to prove, if these matrices achieve the information theoretically minimal number of measurements (up to constant factors). We make substantial progress in this problem. Moreover, we use the tools developed here to prove new connections between RIP and combinatorial list decoding of error-correcting codes. Although compressed sensing has used tools from coding theory since its beginning, this is perhaps the first time that classical coding theory directly benefits from compressed sensing research.