John Urschel
urschel AT mit DOT edu
I am an assistant professor in the MIT Math department and a Junior Fellow at the Harvard Society of Fellows. My research is focused on matrix analysis and numerical analysis, with an emphasis on theoretical results and provable guarantees for practical problems.
Previously, I was a member of the Institute for Advanced Study, under the supervision of Peter Sarnak.
I completed my PhD in math at MIT in 2021, and had the pleasure of being advised by Michel Goemans.
My thesis, Graphs, Principal Minors, and Eigenvalue Problems, was recently awarded the SIAM DiPrima Prize.
I also recently received the SIAM Early Career Prize in Linear Algebra.
Here are a few selected publications:
- Average Nodal Count and the Nodal Count Condition for Graphs, Preprint [PDF]
- A New Upper Bound for the Growth Factor in Gauss. Elimin. with Complete Pivoting, Preprint [PDF]
- Nodal Decompositions of a Symmetric Matrix, International Math. Research Notices (2024) [PDF]
- Maximum Spread of Graphs and Bipartite Graphs, Communications of the AMS (2022) [PDF]
Below, you can find a brief description of my research, a full list of my publications, my current and past teaching, and some outreach programs I am involved in.
Here is a (most likely outdated) CV.
Research:
My interests largely consist of topics in matrix analysis and numerical analysis, many of which are motivated by problems from other areas of mathematics, such as combinatorics, machine learning, probability, and theoretical computer science. A brief description of these two topics and my interests follows.
Matrix Analysis: Linear algebra is a fundamental subject, underpinning almost all areas of mathematics. Matrix analysis, broadly defined, is the study of basis-dependent linear algebra. This additional structure is often crucial -- linear maps encountered in practice may have some special property in a given basis, such as sparsity, symmetry, or non-negativity. I am especially interested in spectral graph theory, the study of a discrete graph/network through the analysis of spectral properties of a matrix representation of it.
Selected Publications:
- Average Nodal Count and the Nodal Count Condition for Graphs, Preprint [PDF]
- Nodal Decompositions of a Symmetric Matrix, International Math. Research Notices (2024) [PDF]
- Maximum Spread of Graphs and Bipartite Graphs, Communications of the AMS (2022) [PDF]
- Learning Determinantal Point Processes with Moments and Cycles, ICML (2017) [PDF]
Numerical Analysis: The field of numerical analysis is primarily concerned with finding efficient and accurate approximate solutions to problems in mathematics. Topics include the numerical solution to linear systems, non-linear equations, eigenvalue problems, numerical differentiation or integration, differential equations, and other problems. I am particularly interested in numerical linear algebra and the solution of linear systems Ax = b and eigenvalue problems Ax = λx. My research is mostly focused on matrix factorizations and moment-based algorithms.
Selected Publications:
- A New Upper Bound for the Growth Factor in Gauss. Elimin. with Complete Pivoting, Preprint [PDF]
- Some New Results on the Maximum Growth Factor in Gaussian Elimination, SIMAX (2024) [PDF]
- Uniform Error Estimates for the Lanczos Method, SIMAX (2021) [PDF]
- On the Characterization and Uniqueness of Centroidal Voronoi Tessellations, SINUM (2017) [PDF]
Papers:
✷ = selected publication, u = undergraduate research project
-
Average Nodal Count and the Nodal Count Condition for Graphs✷,
with Lior Alon.
arXiv Preprint, 2024. [PDF]
-
Recovering a Magnitude-Symmetric Matrix from its Principal Minors,
with Victor-Emmanuel Brunel.
Linear Algebra and its Applications, to appear. [PDF]
-
On the Frobenius Norm of the Inverse of a Non-Negative Matrixu,
with Elsa Frankel.
arXiv Preprint, 2024. [PDF]
-
On a Perturbation Analysis of Higham Squared Maximum Gaussian Elimination Growth Matrices,
with Alan Edelman, Bowen Zhu.
arXiv Preprint, 2024. [PDF] (see Bowen's associated thesis here)
-
A New Upper Bound for the Growth Factor in Gaussian Elimination with Complete Pivoting✷u,
with Ankit Bisain, Alan Edelman.
arXiv Preprint, 2023. [PDF]
-
Estimating the Matrix p -> q Norm,
with Larry Guth, Dominique Maldague.
arXiv Preprint, 2023. [PDF]
-
Nodal Decompositions of a Symmetric Matrix✷,
with Theo McKenzie.
International Math. Research Notices, 2024. [PDF]
-
Some New Results on the Maximum Growth Factor in Gaussian Elimination,
with Alan Edelman.
SIAM Journal on Matrix Analysis, 2024. [PDF]
-
Hamilton Powers of Eulerian Digraphsu,
with Enrico Colón.
Electronic Journal of Combinatorics, 2024. [PDF]
-
Representing the Special Linear Group with Block Unitriangular Matrices,
PNAS Nexus, 2023. [PDF]
-
Maximum Spread of Graphs and Bipartite Graphs✷,
with Jane Breen, Alex Riasanovsky, Michael Tait.
Communications of the AMS, 2022. [PDF]
-
Graphs, Principal Minors, and Eigenvalue Problems,
PhD Thesis, MIT, 2021. [PDF]
-
Regarding Two Conjectures on Clique and Biclique Partitionsu,
with Dhruv Rohatgi, Jake Wellens.
Electronic Journal of Combinatorics, 2021. [PDF]
-
Multidimensional Scaling: Approximation and Complexity,
with Erik Demaine, Adam Hesterberg, Frederic Koehler, Jayson Lynch.
Proceedings of the 38th International Conference on Machine Learning (ICML 2021). [PDF]
-
Uniform Error Estimates for the Lanczos Method.
SIAM Journal on Matrix Analysis, 2021. [PDF]
-
Discrete Trace Theorems and Energy Minimizing Spring Embeddings of Planar Graphs,
with Ludmil Zikatanov.
Linear Algebra and its Applications, 2021. [PDF]
-
Testing Gap k-Planarity is NP-Complete,
with Jake Wellens.
Information Processing Letters, 2021. [PDF]
-
Nodal Decompositions of Graphs.
Linear Algebra and its Applications, 2018. [PDF]
-
Maximum Likelihood Estimation of Determinantal Point Processes,
with Victor-Emmanuel Brunel,Ankur Moitra, Philippe Rigollet.
arXiv Technical Report, 2017. [PDF]
-
On the Characterization and Uniqueness of Centroidal Voronoi Tessellations.
SIAM Journal on Numerical Analysis, 2017. [PDF]
-
Learning Determinantal Point Processes with Moments and Cycles,
with Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet.
Proceedings of the 34th International Conference on Machine Learning (ICML 2017). [PDF]
-
Rates of Estimation for Determinantal Point Processes,
with Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet.
Proceedings of the 30th Annual Conference on Learning Theory (COLT 2017). [PDF]
-
On the Approximation of Laplacian Eigenvalues in Graph Disaggregation,
with Xiaozhe Hu, Ludmil Zikatanov.
Linear and Multilinear Algebra, 2017. [PDF]
-
On the Maximal Error of Spectral Approximation of Graph Bisection,
with
Ludmil Zikatanov.
Linear and Multilinear Algebra, 2016. [PDF]
-
A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians,
with Xiaozhe Hu, Jinchao Xu, Ludmil Zikatanov.
Journal of Computational Mathematics, 2015. [PDF]
-
Spectral Bisection of Graphs and Connectedness,
with Ludmil Zikatanov.
Linear Algebra and its Applications, 2014. [PDF]
-
Graph-Based Topics in Applied Mathematics,
Master's Thesis, Penn State, 2013. [PDF]
-
A Space-Time Multigrid Method for the Numerical Valuation of Barrier Options,
Communications in Mathematical Finance, 2013. [PDF]
-
Instabilities in the Sun-Jupiter-Asteroid Three Body Problemu,
with Joseph Galante.
Celestial Mechanics and Dynamical Astronomy, 2013. [PDF]
Courses:
-
18.335: Introduction to Numerical Methods,
MIT, Spring 2024
-
18.330: Introduction to Numerical Analysis,
MIT, Fall 2023
-
Math 232: Integral Vector Calculus,
Penn State, Fall 2013
-
Math 041: Trigonometry and Analytic Geometry,
Penn State, Spring 2013
Outreach:
Here are a few programs outside of my core responsibilities as an academic mathematician that I take part in. If you are a K-12 math teacher or student, some of these programs may be of interest to you.
MathROOTS: MathROOTS is a two-week summer program hosted by MIT Math for high-potential high school students from underrepresented backgrounds or underserved communities. I am in charge of the academic side of the program. More details can be found here.
Mathical: The Mathical Book Prize, awarded by MSRI, is an annual award for fiction and non-fiction books that inspire children of all ages to see math in the world around them. I am a chair of the selection committee, and am more broadly involved in the dissemination of these fantastic books. More details can be found here.
MoMath: The National Museum of Mathematics highlights the role of math in illuminating the patterns and structures all around us. I serve on the board of the museum and am involved in the exhibits and programming of the museum. More details can be found here.
© 2020 John Urschel -- template shamelessly stolen from Tselil Schramm.
Accessibility