Matthew Kwan

Office: I21.O1.108 (first floor, office building west)
Institute of Science and Technology Austria (ISTA)
Am Campus 1
A-3400 Klosterneuburg
Austria

Hi! Since September 2021, I am Assistant Professor at ISTA. My research is currently supported by an ERC Starting Grant on “Randomness and structure in combinatorics” from the European Commission.

Previously, I was Szegő Assistant Professor in the mathematics department of Stanford University, and before that my doctoral studies were at ETH Zurich under the guidance of Benny Sudakov. You can find my full CV here.

Those looking to join my group as students or postdocs should apply for the ISTA graduate school or the ISTA-fellow program. I am not currently taking interns.

Together with the groups of Herbert Edelsbrunner and Uli Wagner I am hosting the Combinatorics, Geometry and Topology Seminar, and together with the group of Tim Browning I am hosting the Discrete Analysis Days.

Current research group

• Michael Anastos (FWF ESPRIT fellow)
• Alex Grebennikov (PhD student)
• Lenka Kopfová (PhD student)
• Kalina Petrova (IST-BRIDGE fellow)
• Farhood Roostamkhani (PhD student)
• Yiting Wang (PhD student)

Selected research papers

(A complete list of papers is available here)

• High-girth Steiner triple systems (with Ashwin Sah, Mehtaab Sawhney and Michael Simkin). Annals of Mathematics 200.3 (2024), 1059–1156.

  Almost all Steiner triple systems are almost resolvable (with Asaf Ferber). Forum of Mathematics, Sigma 8:E39 (2020).

  Almost all Steiner triple systems have perfect matchings. Proceedings of the London Mathematical Society 121.6 (2020), 1468–1495.

  In the theory of combinatorial design, a Steiner triple system of order n is a system of 3-element subsets (“triples”) of a ground set of size n, such that every pair of elements in the ground set is contained in exactly one triple. Traditional examples of Steiner triple systems (and combinatorial designs more generally) tend to be constructed from rigid algebraic objects, but recent advances have made it possible to apply probabilistic methods in design theory.

  In a first paper, we introduce some general methods for studying random designs, and use these to show that for any n divisible by 3, almost all order-n Steiner triple systems have a perfect matching. In a second paper, we extend these ideas to show that almost all such Steiner triple systems in fact admit a decomposition of almost all their triples into disjoint perfect matchings. That is, almost all Steiner triple systems are almost resolvable. In a third paper, we use probabilistic ideas to prove the existence of “locally sparse” Steiner triple systems with arbitrarily high girth, resolving an old conjecture of Erdős.

  Here is a recording of one of my talks that featured the first two of these results. Here is a Quanta magazine article on the third of these results.

• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture (with Ashwin Sah, Lisa Sauermann and Mehtaab Sawhney). Forum of Mathematics, Pi 11:E21 (2023).

  An algebraic inverse theorem for the quadratic Littlewood–Offord problem, and an application to Ramsey graphs (with Lisa Sauermann). Discrete Analysis 2020:12 (2020).

  Ramsey graphs induce subgraphs of quadratically many sizes (with Benny Sudakov). International Mathematics Research Notices 2020.6 (2020), 1621–1638.

  Proof of a conjecture on induced subgraphs of Ramsey graphs (with Benny Sudakov). Transactions of the American Mathematical Society 372 (2019), 5571–5594.

  An n-vertex graph is called C-Ramsey if it has no clique or independent set of size C log n. All known constructions of Ramsey graphs involve randomness in an essential way, and there is a line of research towards showing that in fact all Ramsey graphs must obey certain “richness” properties characteristic of random graphs. In these papers we study various statistical properties of Ramsey graphs, in particular resolving longstanding conjectures of Erdős and McKay and of Erdős, Faudree and Sós. A main theme in these papers is the development of connections to small-ball probability for polynomials of independent random variables.

• The exact rank of sparse random graphs (with Margalit Glasgow, Ashwin Sah and Mehtaab Sawhney). Journal of the European Mathematics Society, to appear.

  Singularity of the k-core of a random graph (with Asaf Ferber, Ashwin Sah and Mehtaab Sawhney). Duke Mathematical Journal 172.7 (2023), 1293–1332.

  Although very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), we prove in various senses that this is only due to “low-degree dependencies”. First, resolving a conjecture of Vu, we prove that for any fixed k ≥ 3 and c > 0, a random graph with n vertices and edge probability c/n typically has the property that its k-core (its maximal subgraph with minimum degree at least k) is nonsingular. Then, in a second paper, we refine this result by giving a combinatorial characterisation of the rank of a sparse random graph.

• Exponential anticoncentration for the permanent (with Zach Hunter and Lisa Sauermann). To be submitted.

  On the permanent of a random symmetric matrix (with Lisa Sauermann). Selecta Mathematica 8.15 (2022).

  There is a huge body of work on singularity and determinants of (discrete) random matrices, and most of these results are believed to have analogues for permanents. However, permanents have no geometric or linear-algebraic interpretation, and almost all the available tools break down. In these papers we prove some of very few known rigorous results in this direction.

  In a first paper, resolving a conjecture of Vu we prove that the permanent of a uniformly random symmetric n×n matrix with ±1 entries typically has magnitude n^{n/2 + o(n)} (this extends a result of Tao and Vu to the symmetric setting). In a second paper, we prove that the permanent of a uniformly random n×n matrix with ±1 entries is exponentially anticoncentrated (this is a permanent analogue of a celebrated result of Kahn, Komlós and Szemerédi).

• Resolution of the quadratic Littlewood–Offord problem (with Lisa Sauermann). Compositio Mathematica, to appear.

  Geometric and o-minimal Littlewood–Offord problems (with Jacob Fox and Hunter Spink). Annals of Probability 51.1 (2023), 101–126.

  Resilience for the Littlewood–Offord Problem (with Afonso Bandeira and Asaf Ferber). Advances in Mathematics 319 (2017), 292–312.

  The classical Littlewood–Offord problem is concerned with anticoncentration of sums of independent random variables: what general upper bounds can be proved on the probability that such a sum is equal to a particular value? More generally, the polynomial Littlewood–Offord problem is concerned with anticoncentration of low-degree polynomials of independent random variables.

  In a first paper, we introduce and solve a “resilience” version of the Littlewood–Offord problem, studying the extent to which adversarial changes to the underlying random variables can affect anticoncentration. In a second paper, we introduce some geometric variants of the Littlewood–Offord problem, and in a third paper we use this geometric point of view, together with a new inductive decoupling technique, to prove an optimal general bound for the quadratic Littlewood–Offord problem.

• Extension complexity of low-dimensional polytopes (with Lisa Sauermann and Yufei Zhao). Transactions of the American Mathematical Society 375 (2022), 4209–4250.

  Sometimes, it is possible to represent a complicated polytope as a “shadow” of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets in a (possibly higher-dimensional) polytope from which P can be obtained as a linear projection. It is an important question to understand the extent to which the extension complexity of a polytope is controlled by its dimension, and in this paper we prove three different results along these lines. First, we show that there exists an n^o(1)-dimensional polytope with at most n facets and extension complexity n^1−o(1). Second, we obtain optimal bounds for the extension complexity of random d-polytopes, and third, we obtain an optimal upper bound for the extension complexity of cyclic polygons (all of whose vertices lie on a common circle).

  Here is a recording of a talk I gave on the results in this paper.

• Halfway to Rota's basis conjecture (with Matija Bucic, Alexey Pokrovskiy and Benny Sudakov). International Mathematics Research Notices, 2020.21 (2020), 8007–8026.

  Given n bases B₁,...,B_n in an n-dimensional vector space V, a transversal basis is a basis of V containing exactly one element from each B_i. Rota's basis conjecture posits that it is always possible to find n disjoint transversal bases. In this paper we prove the partial result that one can always find (1/2 − o(1)) n disjoint transversal bases. Our result generalises to the setting of matroids.

  Here is a recording of a talk in which I gave a fairly complete outline of the proof of this theorem.

• List-decodability with large radius for Reed–Solomon codes (with Asaf Ferber and Lisa Sauermann). IEEE Transactions on Information Theory 68.6 (2022), 3823–3828. A conference version appeared at FOCS 2021.

  Entangled states are typically incomparable (with Vishesh Jain and Marcus Michelen). Submitted.

  Smoothed analysis for graph isomorphism (with Michael Anastos and Benjamin Moore). Submitted. A conference version appeared at STOC 2025.

  These are some of my most successful “interdisciplinary” works (concerning questions of interest outside the mathematics community).

  First, we show that a class of error-correcting codes called Reed–Solomon codes have nearly optimal list-decodability properties (improving a result of Guo, Li, Shangguan, Tamo and Wootters, and resolving the motivating question of their work). Second, we resolve an old conjecture of Nielsen in quantum information theory, showing that for two randomly entangled quantum states, it is typically not possible to convert from one to the other by “local operations with classical communication”. Third, extending a classical theorem of Babai, Erdős and Selkow, we show that naïve combinatorial refinement algorithms are extremely efficient for graph isomorphism testing, under mild random perturbation (this is the so-called smoothed analysis philosophy for analysis of algorithms, due to Spielman and Teng).