]. N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld et al., Testing k-wise and almost k-wise independence, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , STOC '07, pp.496-505, 2007.
DOI : 10.1145/1250790.1250863
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.4337

N. Alon, S. Arora, R. Manokaran, D. Moshkovitz, and O. Weinstein, Inapproximability of densest ?-subgraph from average-case hardness, 2011.

N. Alon, O. Goldreich, J. Hastad, and R. Peralta, Simple Construction of Almost k-wise Independent Random Variables, Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp.544-553, 1990.

N. Alon, M. Krivelevich, and B. Sudakov, Finding a large hidden clique in a random graph, Random Structures and Algorithms, vol.13, issue.3-4, pp.457-466, 1998.
DOI : 10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.4033

N. Alon, M. Krivelevich, and V. Vu, On the concentration of eigenvalues of random symmetric matrices, Israel Journal of Mathematics, vol.67, issue.1, pp.259-267, 2002.
DOI : 10.1007/BF02785860

A. Bandeira, E. Dobriban, D. Mixon, and W. Sawin, Certifying the restricted isometry property is hard. arxiv.org/abs, 1204.

J. Bourgain, S. J. Dilworth, K. Ford, S. Konyagin, and D. Kutzarova, Explicit Constructions of RIP Matrices and Related Problems Available at arxiv:1008, 2010.
DOI : 10.1215/00127094-1384809
URL : http://arxiv.org/abs/1008.4535

J. Bourgain, S. J. Dilworth, K. Ford, S. Konyagin, and D. Kutzarova, Breaking the k 2 Barrier for Explicit RIP Matrices, Proceedings of the Symposium on Theory of Computing (STOC), 2011.

E. J. Candès, The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathematique, vol.346, issue.9-10, pp.589-592, 2008.
DOI : 10.1016/j.crma.2008.03.014

E. J. Candès, J. K. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Communications on Pure and Applied Mathematics, vol.7, issue.8, pp.591207-1223, 2006.
DOI : 10.1002/cpa.20124

E. J. Candès and T. Tao, Decoding by Linear Programming. Information Theory, IEEE Transactions on, vol.51, issue.12, pp.4203-4215, 2005.

A. Aspremont, F. Bach, and L. Ghaoui, Optimal Solutions for Sparse Principal Component Analysis, J. Mach. Learn. Res, vol.9, pp.1269-1294, 2008.

A. Aspremont and L. Ghaoui, Testing the Nullspace Property using Semidefinite Programming Available at arxiv:0807, Mathematical Programming, pp.123-144, 2011.

R. A. Devore, Deterministic constructions of compressed sensing matrices, Journal of Complexity, vol.23, issue.4-6, pp.918-925, 2007.
DOI : 10.1016/j.jco.2007.04.002

Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica, vol.67, issue.3, pp.233-241, 1981.
DOI : 10.1007/BF02579329

E. Hazan and R. Krauthgamer, How Hard Is It to Approximate the Best Nash Equilibrium?, SIAM Journal on Computing, vol.40, issue.1, pp.79-91, 2011.
DOI : 10.1137/090766991

A. Juditsky and A. Nemirovski, On verifiable sufficient conditions for sparse signal recovery via ??? 1 minimization, Mathematical Programming, pp.57-88, 2011.
DOI : 10.1007/s10107-010-0417-z
URL : https://hal.archives-ouvertes.fr/hal-00321775

B. S. Kashin, The Diameters of Octahedra, Uspekhi Mat. Nauk, vol.30, pp.251-252, 1975.

P. Koiran and A. Zouzias, On the certification of the restricted isometry property. arxiv.org/abs/1103, 2011.

M. Pfetsch and A. Tillmann, The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing. arxiv.org/abs, 1205.