Current Research Interests

• Probability theory, Mathematics of data science, Mathematical physics

People

• Yiming Xu (postdoc, 2023-)
• Justin Ko (postdoc, 2023-)
• Parsa Rangriz (MMath Stat, 2023-)
• Aseem Baranwal (PhD CS, 2020- )
• Victor Issa (ENS M2 Intern, 2023, now at ENS Lyons)
• Tingzhou Yu (MMath Stat, 2023, now at U. Alberta)
• Philipp Schroeppel (MMath Stat, 2022, now at Ulm U.)
• Anna Brandenberger (MSc, Perimeter Institute, 2022, now at MIT)

Publications and preprints

1. Finding planted cliques using Markov Chain Monte Carlo

   with R. Gheissari and Y. Xu,

   arXiv

2. Shattering in the Ising pure p-spin model

   with D. Gamarnik and E. Kizildag,

   arXiv

3. Existence of the free energy for heavy-tailed spin glasses

   with P. Lopatto,

   arXiv

4. Differentially private multivariate medians

   with K. Ramsay and S. Chenouri,

   arXiv

5. Circuit lower bounds for the p-spin optimization problem,

   with D. Gamarnik and A. S. Wein,

   Markov Processes and Related Fields (special issue for IRS 2022) (to appear)

6. High-dimensional SGD aligns with emerging outlier eigenspaces

   with G. Ben Arous, R. Gheissari, and J. Huang,

   International Conference on Learning Representations 12 (ICLR 2024) (spotlight)

7. Hardness of random optimization problems for boolean circuits, low-degree polynomials, and Langevin dynamics,

   with D. Gamarnik and A. S. Wein,

   SIAM Journal on Computing 53 no. 1 (2024) 1-46

8. High-dimensional limit theorems for SGD: Effective dynamics and critical scaling

   with G. Ben Arous and R. Gheissari,

   Communications on Pure and Applied Mathematics 77 no. 3 (2024) 2030-2080

   Extended abstract appeared in NeurIPS 2022 (Outstanding Paper Award)

9. Shattering versus metastability in spin glasses,

   with G. Ben Arous,

   Communications on Pure and Applied Mathematics 77 no. 1 (2024) 139-176

10. Optimality of Message-Passing Architectures for Sparse Graphs

    with A. Baranwal and K. Fountoulakis,

    Advances in Neural Information Processing Systems 37 (NeurIPS) 2023

11. Graph attention retrospective

    K. Fountoulakis, A. Levi, S. Yang, A. Baranwal and A.J.,

    Journal of Machine Learning Research 24 no. 246 (2023) 1-52

12. Effects of Graph Convolutions in Multi-Layer Networks

    with A. Baranwal and K. Fountoulakis,

    International Conference on Learning Representations 11 (ICLR) 2023 (spotlight)

13. A simple construction of the dynamical Φ⁴₃ model,

    with N. Perkowski,

    Transactions of the American Mathematical Society 376 no. 3 (2023) 1507–1522

14. The overlap gap property in principal submatrix recovery,

    with D. Gamarnik and S. Sen,

    Probability Theory and Related Fields 181 (2021) 757–814

15. Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization,

    with A. Baranwal and K. Fountoulakis,

    International Conference on Machine Learning 38 (ICML 2021) (spotlight)

    Proceedings of Machine Learning Research 139 (2021) 684-693

16. Online stochastic gradient descent on non-convex losses from high-dimensional inference,

    with G. Ben Arous and R. Gheissari,

    Journal of Machine Learning Research 22 no. 106 (2021) 1-51

17. On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model,

    with S. Sen,

    Annales de l'Instut Henri Poincaré D Comb. Phys. Inter. 8 (2021) 35-88.

18. The overlap gap property and approximate message passing algorithms for p-spin models,

    with D. Gamarnik,

    The Annals of Probability 49 no. 1 (2021) 180-205

19. Low degree hardness of random optimization problems,

    with D. Gamarnik and A. S. Wein

    Foundations of Computer Science (FOCS) (2020) 131-140

20. Statistical thresholds for tensor PCA,

    with P. Lopatto and L. Miolane,

    The Annals of Applied Probability 30 no. 4 (2020) 1910-1933

21. Algorithmic thresholds for tensor PCA,

    with G. Ben Arous and R. Gheissari,

    The Annals of Probability 48 no. 4 (2020) 2052-2087

22. Bounding flows for spherical spin glass dynamics,

    with G. Ben Arous and R. Gheissari,

    Communications in Mathematical Physics 373 (2020) 1011-1048

23. Dynamics of mean field spin glasses on short and long timescales,

    Journal of Mathematical Physics 60, 083305 (2019)

24. Thouless–Anderson–Palmer equations for generic p-spin glasses,

    with A. Auffinger,

    The Annals of Probabability 47 no. 43 (2019) 2230-2256

25. On the spectral gap of spherical spin glass dynamics,

    with R. Gheissari,

    Annales de l'Institut Henri Poincaré B Probab. et Stat. 55 no. 2 (2019) 756-776

26. On spin distributions for generic p-spin models,

    with A. Auffinger,

    Journal of Statistical Physics (2019) 174-316

27. Spectral gap estimates in mean field spin glasses,

    with G. Ben Arous,

    Communications in Mathematical Physics 361 no. 1 (2018) 1-52

28. MAX κ-CUT and the inhomogeneous Potts spin glass,

    with J. Ko and S. Sen,

    The Annals of Applied Probability 28 no. 3 (2018) 1536–1572

29. Bounding the complexity of replica symmetry breaking for spherical spin glasses,

    with I. Tobasco,

    Proceedings of the American Mathematical Society 146 (2018) 3127-3142

30. Random matrices and the New York City subway system,

    with T. Trogdon,

    Physical Review E 96, 030101(R) (2017)

31. Low temperature asymptotics of spherical mean field spin glasses,

    with I. Tobasco,

    Communications in Mathematical Physics 352 no. 3 (2017) 979-1017

32. Some properties of the phase diagram for mixed p-spin glasses,

    with I. Tobasco,

    Probability Theory and Related Fields 167 (2017) 615-672 (slides)

33. Approximate ultrametricity for random measures with applications to spin glasses,

    Communications on Pure and Applied Mathematics 70 (2017) 611–664 (video)

34. A dynamic programming approach to the Parisi functional,

    with I. Tobasco,

    Proceedings of the American Mathematical Society 144 (2016) 3135-3150

35. On the overlap distribution of branching random walks,

    Electronic Journal of Probability 21 no. 50 (2016) 16 pp.

36. Variational and Structural Methods in Mean Field Spin Glasses,

    Ph.D. Thesis, May 2016

37. Solution of the propeller conjecture in R³,

    with S. Heilman and A. Naor

    Discrete & Compututational Geometry 50 (2013) 263-305 (code)

    Extended abstract appeared at STOC 2012.

38. Charged particle motion in electromagnetic fields varying moderately slowly in space,

    with H. Weitzner,

    Physics of Plasmas 18, 104510 (2011)