A classical theorem of Dirac states that any graph on n vertices with minimum degree at least n/2 contains a Hamiltonian cycle, an edge-traversing cycle that visits each vertex in the graph exactly once. Since Dirac's theorem, researchers have found lower bounds on the number of Hamiltonian cycles a graph contains as a function of its minimum degree. These bounds aren't too far away from what one would expect to see in a typical random graph with appropriate edge probability. Here we contribute to the line of research that seeks to extend these results to k-uniform hypergraphs, where cycles are now chains of edges whose consecutive links overlap with one another in some fixed number, \ell, of vertices. We show that the number of so-called \ell-cycles in hypergraphs with sufficiently high co-degree is at least, up to a sub-exponential factor, what one would expect to see in a typical random hypergraph with appropriate (hyper)edge probability.

Joint work with Asaf Ferber and Adva Mond (University of Cambridge).

This is a continuation of my talk last quarter on Sharp Matrix Concentration. In this talk, I will give a proof for a special case of the main result. The proof consists of two parts. The linear algebra part is on a quantitative estimate about noncommutativity. The other part involves combinatorics. If time permits, I will briefly talk about the analytic proof of the main result that works in general. Paper: https://arxiv.org/abs/2104.02662

For a function observed through point evaluations, is there an optimal way to recover it or merely to estimate a dependent quantity? I will give an affirmative answer to this data-focused question, especially  under the assumption that the function belongs to a model set defined by approximation capabilities.  In fact, I will uncover computationally implementable linear recovery maps that are optimal in the worst-case setting. I will present some recent and ongoing works extending the theory in several directions, with particular emphasis put on observations that are inexact---adversarially or randomly.

Recent theoretical understanding of neural networks has connected their training and generalization to associated kernel matrices. Due to the nonlinearity of the activation function, at random initialization, these kernel matrices are non-linear random matrices.  We consider the limiting spectral distributions of conjugate kernel and neural tangent kernel matrices for two-layer neural networks with deterministic data and random weights. When the width of the network grows faster than the size of the dataset, a deformed semicircle law appears. In this regime, we can also calculate the asymptotic testing and training errors for random feature regression. Joint work with Zhichao Wang https://arxiv.org/abs/2109.09304.

Over the last couple of decades, the theory of interacting particle systems has found some unexpected connections to orthogonal polynomials, symmetric functions, and various combinatorial structures. The asymmetric simple exclusion process (ASEP) has played a central role in this connection. Recently, Cantini, de Gier, and Wheeler found that the partition function of the multispecies ASEP on a circle is a specialization of a Macdonald polynomial $P_{\lambda}(X;q,t)$. Macdonald polynomials are a family of symmetric functions that are ubiquitous in algebraic combinatorics and specialize to or generalize many other important special functions. Around the same time, Martin gave a recursive formulation expressing the stationary probabilities of the ASEP on a circle as sums over combinatorial objects known as multiline queues, which are a type of queueing system. Shortly after, with Corteel and Williams we generalized Martin's result to give a new formula for $P_{\lambda}$ via multiline queues.

The modified Macdonald polynomials $\widetilde{H}_{\lambda}(X;q,t)$ are a version of $P_{\lambda}$ with positive integer coefficients. A natural question was whether there exists a related statistical mechanics model for which some specialization of $\widetilde{H}_{\lambda}$ is equal to its partition function. With Ayyer and Martin, we answer this question in the affirmative with the multispecies totally asymmetric zero-range process (TAZRP), which is a specialization of a more general class of zero range particle processes. We introduce a new combinatorial object in the flavor of the multiline queues, which on one hand, expresses stationary probabilities of the mTAZRP, and on the other hand, gives a new formula for $\widetilde{H}_{\lambda}$. We define an enhanced Markov chain on these objects that lumps to the multispecies TAZRP, and then use this to prove several results about particle densities and correlations in the TAZRP.