Publications

Mathematical proof
  1. H. Huang, M. Rudelson, K. Tikhomirov, Well-invertible column subsets of sparse matrices are rare, submitted.
  2. S. Chenakkod, M. Derezinski, X. Dong, M. Rudelson, Well-conditioned oblivious perturbations in linear space, to appear in SODA 2026.
  3. H. Huang, M. Rudelson, Hardness of approximation of centered convex bodies by polytopes, to appear in Advances in Math.
  4. M. Rudelson, A large deviation inequality for the rank of a random matrix, Ann. Probab. 52 (2024), no. 5, 1992–2018.
  5. S. Chenakkod, M. Derezinski, X. Dong, M. Rudelson, Optimal embedding dimension for sparse subspace embeddings, STOC 2024, Association for Computing Machinery (ACM), New York, 2024, 1106–1117.
  6. X. Dong, M. Rudelson, Approximately Hadamard matrices and Riesz bases in random frames, Int. Math. Res. Not. (2024), no. 3, 2044–2065.
  7. A. Barvinok, M. Rudelson, A quick estimate for the volume of a polyhedron, Israel J. Math. 262 (2024), no. 1, 449–473.
  8. C. Mao, M. Rudelson, K. Tikhomirov, Exact matching of random graphs with constant correlation, Probab. Theory Related Fields 186 (2023), no. 1–2, 327–389.
  9. A. Barvinok, M. Rudelson, When a system of real quadratic equations has a solution, Adv. Math. 403 (2022), Paper No. 108391, 38 pp.
  10. C. Mao, M. Rudelson, K. Tikhomirov, Random graph matching with improved noise robustness, COLT 2021.
  11. A. Basak, M. Rudelson, Sharp transition of the invertibility of the adjacency matrices of sparse random graphs, Probab. Theory Related Fields 180 (2021), no. 1–2, 233–308.
  12. H. König, M. Rudelson, On the volume of non-central sections of a cube, Adv. Math. 360 (2020), 106929, 30 pp.
  13. H. Huang, M. Rudelson, Size of nodal domains of the eigenvectors of a G(n,p) graph, Random Structures Algorithms 57 (2020), no. 2, 393–438.
  14. M. Rudelson, K. Tikhomirov, The sparse circular law under minimal assumptions, Geom. Funct. Anal. 29 (2019), no. 2, 561–637.
  15. A. Basak, M. Rudelson, The circular law for sparse non-Hermitian matrices, Ann. Probab. 47 (2019), no. 4, 2359–2416.
  16. M. Rudelson, Delocalization of eigenvectors of random matrices, Random Matrices, IAS/Park City Mathematics Series, vol. 26 (2019), 303–340.
  17. S. P. Kasiviswanathan, M. Rudelson, Restricted eigenvalue from stable rank with applications to sparse linear regression, COLT 2018 (31st Annual Conference on Learning Theory).
  18. M. Rudelson, S. Zhou, Errors-in-variables models with dependent measurements, Electron. J. Stat. 11 (2017), no. 1, 1699–1797.
  19. A. Basak, M. Rudelson, Invertibility of sparse non-Hermitian matrices, Adv. Math. 310 (2017), 426–483.
  20. M. Rudelson, R. Vershynin, No-gaps delocalization for general random matrices, Geom. Funct. Anal. 26 (2016), no. 6, 1716–1776.
  21. M. Rudelson, A. Samorodnitsky, O. Zeitouni, Hafnians, perfect matchings and Gaussian matrices, Ann. Probab. 44 (2016), no. 4, 2858–2888.
  22. M. Rudelson, On the complexity of the set of unconditional convex bodies, Discrete Comput. Geom. 55 (2016), no. 1, 185–202.
  23. M. Rudelson, O. Zeitouni, Singular values of Gaussian matrices and permanent estimators, Random Structures Algorithms 48 (2016), no. 1, 183–212.
  24. M. Rudelson, R. Vershynin, Small ball probabilities for linear images of high dimensional distributions, IMRN 2015, no. 19, 9594–9617.
  25. S. P. Kasiviswanathan, M. Rudelson, Spectral norm of random kernel matrices with applications to privacy, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 898–914, LIPIcs, Leibniz International Proceedings in Informatics, 2015.
  26. M. Rudelson, R. Vershynin, Delocalization of eigenvectors of random matrices with independent entries, Duke Math. J. 164 (2015), no. 13, 2507–2538.
  27. M. Rudelson, R. Vershynin, Hanson–Wright inequality and sub-Gaussian concentration, Electron. Commun. Probab. 18 (2013), no. 82, 9 pp.
  28. M. Rudelson, Recent developments in non-asymptotic theory of random matrices, Modern Aspects of Random Matrix Theory, AMS Proceedings of Symposia in Applied Mathematics, 2014, pp. 83–121.
  29. A. Litvak, M. Rudelson, N. Tomczak-Jaegermann, Approximation by projections of polytopes with few facets, Israel J. Math. 203 (2014), no. 1, 141–160.
  30. M. Rudelson, R. Vershynin, Invertibility of random matrices: unitary and orthogonal perturbations, J. Amer. Math. Soc. 27 (2014), no. 2, 293–338.
  31. S. Kasiviswanathan, M. Rudelson, A. Smith, The power of linear reconstruction attacks, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2013).
  32. M. Rudelson, S. Zhou, Reconstruction from anisotropic random measurements, IEEE Trans. Inform. Theory 59 (2013), no. 6, 3434–3447.
  33. M. Rudelson, Row products of random matrices, Adv. Math. 231 (2012), no. 6, 3199–3231.
  34. M. Rudelson, R. Vershynin, Non-asymptotic theory of random matrices: extreme singular values, Proceedings of the International Congress of Mathematicians, Hyderabad, India, 2010.
  35. S. Kasiviswanathan, M. Rudelson, A. Smith, J. Ullmann, The price of privately releasing contingency tables and the spectra of random matrices with correlated rows, STOC 2010 (42nd ACM Symposium on Theory of Computing).
  36. M. Rudelson, R. Vershynin, The smallest singular value of a random rectangular matrix, Comm. Pure Appl. Math. 62 (2009), no. 12, 1707–1739.
  37. M. Rudelson, R. Vershynin, The least singular value of a random square matrix is O(n−1/2), C. R. Math. Acad. Sci. Paris 346 (2008), no. 15–16, 893–896.
  38. M. Rudelson, R. Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math. 218 (2008), no. 2, 600–633.
  39. M. Rudelson, R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements, Comm. Pure Appl. Math. 61 (2008), no. 8, 1025–1045.
  40. M. Rudelson, Invertibility of random matrices: norm of the inverse, Annals of Mathematics 168 (2008), 575–600.
  41. O. Guedon, M. Rudelson, Lp moments of random vectors via majorizing measures, Adv. Math. 208 (2007), no. 2, 798–823.
  42. M. Rudelson, R. Vershynin, Sampling from large matrices: an approach through geometric functional analysis, J. ACM 54 (2007), no. 4, Art. 21, 19 pp.
  43. M. Rudelson, Norm of the inverse of a random matrix, FOCS 2006 (47th Annual Symposium on Foundations of Computer Science).
  44. M. Rudelson, R. Vershynin, Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements, CISS 2006 (40th Annual Conference on Information Sciences and Systems), invited paper.
  45. M. Rudelson, Lower estimates for the singular values of random matrices, Compt. Rendus Math. de L’Academie des Sciences 342 (2006), no. 4, 247–252.
  46. M. Rudelson, R. Vershynin, Geometric approach to error correcting codes and signal recovery, Int. Math. Res. Not. 2005, no. 64, 4019–4041.
  47. E. Candes, M. Rudelson, T. Tao, R. Vershynin, Error correction via linear programming, FOCS 2005 (46th Annual Symposium on Foundations of Computer Science).
  48. M. Rudelson, R. Vershynin, Combinatorics of random processes and sections of convex bodies, Annals of Mathematics 164 (2006), 603–648.
  49. M. Rudelson, R. Vershynin, Isoperimetry of waists and local versus global convex geometries, appendix to a paper of R. Vershynin, Duke Math. J. 131 (2006), no. 1, 14–16.
  50. S. Mendelson, A. Pajor, M. Rudelson, On the geometry of {+1, −1} polytopes, Discrete Comput. Geom. 34 (2005), no. 3, 365–379.
  51. A. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005), no. 2, 491–523.
  52. A. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, R. Vershynin, Random Euclidean embeddings in spaces of bounded volume ratio, C. R. Math. Acad. Sci. Paris 339 (2004), no. 1, 33–38.
  53. A. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, R. Vershynin, Euclidean embeddings in spaces of finite volume ratio via random matrices, J. Reine Angew. Math. 589 (2005), 1–19.
  54. M. Rudelson, Extremal distances between sections of convex bodies, Geom. Funct. Anal. 14 (2004), no. 5, 1063–1088.
  55. M. Rudelson, R. Vershynin, Embeddings of Levy families into Banach spaces, Geom. Funct. Anal. 12 (2002), no. 1, 183–198.
  56. A. A. Giannopoulos, V. D. Milman and M. Rudelson, Convex bodies with minimal mean width, Geometric Aspects of Functional Analysis, 81–93, Lecture Notes in Math., 1745, Springer, Berlin, 2001.
  57. M. Rudelson, Sections of the difference body, Discrete and Computational Geometry 23 (2000), 137–146.
  58. M. Rudelson, Distances between non-symmetric convex bodies and the MM* estimate, Positivity 4 (2000), no. 2, 161–178.
  59. M. Rudelson, Almost orthogonal submatrices of an orthogonal matrix, Israel J. Math. 111 (1999), 143–155.
  60. M. Rudelson, Random vectors in the isotropic position, J. of Functional Analysis 164 (1999), no. 1, 60–72.
  61. M. Rudelson, Contact points of convex bodies, Israel J. of Math. 101 (1997), 93–124.
  62. M. Avellaneda, A. V. Cherkaev, L. V. Gibiansky, G. W. Milton, M. Rudelson, A complete characterization of the possible bulk and shear moduli of planar polycrystals, J. Mech. Phys. Solids 44 (1996), 1179–1218.
  63. M. Rudelson, Approximate John’s decompositions, Operator Theory: Advances and Applications 77 (1995), 245–249.
  64. M. Rudelson, Estimates of the weak distance between finite-dimensional Banach spaces, Israel J. of Math. 89 (1995), 189–204.
  65. M. Rudelson, A characterization of 2-trivial Banach spaces with an unconditional basis, Zap. Nauchn. Sem. LOMI 157 (1987), 76–87, Russian; English translation in Journal of Soviet Math., 44, no. 6, 800–808.