Abstracts
Giles Gardam
Title: SAT for the working mathematician
Abstract: I will discuss solvers for the Boolean satisfiability problem (SAT) as a tool for the working mathematician. SAT is NP-complete which means it is (in theory) broadly applicable but (in theory) very difficult, however modern SAT solvers are able to solve remarkably large problems in practice. An example of this from my own experience is producing a counterexample to the unit conjecture for group rings, which had remained open for 80 years.
Andras Juhasz
Title: Reinforcement learning and knot theory
Abstract: Several hard problems in knot theory can be formulated as single-player games, including computing the unknotting number and the 4-ball genus, making these amenable to reinforcement learning (RL) algorithms. There has been substantial progress over the past few years, but there is still a gap between what is possible using RL and more classical methods. I will discuss some of the latest results and remaining challenges.
Anders Karlsson
Title: The Pervasive Role of Composing Transformations in Machine Learning
Abstract: From the layer maps of neural networks to training procedures and reinforcement learning, compositions of transformations permeate modern AI. These compositional products often involve randomly selected maps, as in weight initialization, stochastic gradient descent (SGD), and dropout. In reinforcement learning, Bellman-type operators with randomness are iterated to update reward structures and strategies. I will discuss the mathematics and geometry underlying the composition of random transformations. In particular, I will explain a general limit law established in joint work with Gouëzel. Moreover, I will discuss a possible cut-off phenomenon related to the depth of neural networks and the influence of iteration order. Motivated by these observations, and in collaboration with Avelin, Dherin, Gonzalvo, Mazzawi, and Munn, we propose backward variants of SGD that improve stability and convergence while maintaining generalisation.
Alex Lubotzky
Title: Good locally testable codes
Abstract: An error-correcting code is locally testable (LTC) if a random tester reads only a small number of bits of a given word and decides whether the word is in the code, or at least close to it. A long-standing problem asks if there exists such a code that also satisfies the golden standards of coding theory: constant rate and constant distance. Unlike the classical situation in coding theory, random codes are not LTC, so this problem is a challenge of a new kind. We construct such codes based on what we call (Ramanujan) Left/Right Cayley square complexes. These objects seem to be of independent group-theoretic interest. The codes built on them are 2-dimensional versions of the expander codes constructed by Sipser and Spielman (1996). Based on joint work with I. Dinur, S. Evra, R. Livne, and S. Mozes.
Shahar Mendelson
Title: How to overcome the shortcomings of the empirical mean
Abstract: the empirical mean - i.e., the average of the data points one is given - is of obvious importance; for one, it is the most natural guess of the true mean of the sampled object. Unfortunately and perhaps surprisingly, it is often a terrible guess. As a result, there are standard procedures that are based on the empirical mean and are used throughout data science (e.g. empirical risk minimization) whose performance is far from optimal. In this talk I will try to pinpoint the reasons for the suboptimality of the empirical mean and suggest alternatives. I will focus on one indicative example: uniform $L_p$ estimation in a subset of $S^{d-1}$. More accurately, for an isotropic, log-concave random vector $X$ in $R^d$, a set $T \subset S^{d-1}$, and $p> 2$, the question is to find a procedure $\Phi$ that, given $N$ independent copies of $X$ - $X_1,...,X_N$, returns for every $t \in T$ its guess of $E|<X,t>|^p$. The performance of the procedure is measured by the largest error in $T$: $\sup_{t \in T} | \Phi(X_1,...,X_N,t)-E|<X,t>|^p|$. As it happens, the empirical mean $\frac{1}{N}\sum_{i=1}^N |<X_i,t>|^p$ is a bad alternative, but identifying a better one is nontrivial. The solution I will outline opens the door to similar improvements in a variety of problems in data science (joint work with D. Bartl).
Ryan O’Donnell
Title: High-dimensional expanders from group theory... and computer tools
Abstract: In theoretical computer science, an increasingly important role is being played by sparse high-dimensional expanders (HDXs). In turn, the only constructions of these objects that we know are based on groups of Lie type. Most commonly studied are the HDXs based on "A_d-type" groups, yet recent PCPs breakthroughs were only unlocked via the topological properties of more exotic, "C_d-type" HDXs. Motivated by this, we prove new topological properties ("cosystolic/coboundary expansion") of coset complex HDXs over non-A_d-type Chevalley groups. I will describe some of the math, but I will also tell some stories about the computer tools involved. These stories will include:
. Martha Evens's SNOBOL code for her friend's 1979 Northwestern PhD thesis
. The Mayor of Evanston, aged 19
. A ChatGPT video game for solving the Word Problem on groups
. Calculating the rank of a 1million x 2million matrix
. A computer-drawn 'movie' of surface triangulation
. Getting some undergrads to formalize 70 pages of math in Lean
Based on joint work with Noah G. Singer (Carnegie Mellon).
Fedor Pavutnitskiy
Title: LLMs for the Working Mathematician
Abstract: In this introductory talk I will survey foundational and recent works in the emerging area of using large language models (LLMs) in contemporary mathematical research. I will also discuss key challenges we have faced and share progress from our own ongoing projects.
Laura Ciobanu Radomirovic
Title: Word equations, constraints and string solvers
Abstract: In this talk I will give an overview of word equations in free monoids and groups that are `free-like’. I will then discuss how one can express the solutions to word equations as formal languages, and touch upon the (un)decidability of solving word equations with a variety of algebraic and combinatorial constraints. The constraints stem from both theoretical and practical settings, the latter coming from the world of string solvers. If time allows, I will mention recent efforts to solve word equations with reinforcement learning and SMT solvers. This is based on work with V. Diekert and M. Elder, separately with G. Zetzsche, and with/of Albert Garreta.
Lawrence Saul
Title: A curious correspondence between sparse and low-rank matrices and its myriad practical uses
Abstract: We consider when a sparse nonnegative matrix can be recovered, via a simple elementwise nonlinearity, from a real-valued matrix of significantly lower rank. We show that this question arises naturally in many problems of high dimensional data analysis, and for a particular choice of nonlinearity, we describe an algorithm, known as subzero matrix completion, to discover these low-rank representations. As illustrative examples, we use the algorithm to analyze the synaptic weight matrix of the fruit-fly connectome and the co-occurence statistics of words in natural language. Finally, we discuss the challenges of scaling this algorithm to very large matrices, as well as recent progress on overcoming these challenges. (Affiliation: Flatiron Institute)
Shmuel Weinberger
Title: Naive Reflections on the Evolution of Algorithms
Abstract: A common theme views evolution as a kind of iterative dynamical process that attempts to optimize (or even learns an optimizer) according to a loss or fitness function. This talk will describe some very preliminary ideas about one concrete model of this, some of the mathematics it results in (which lie in quantitative topology), some of the directions where it is lacking (and there are many) and possible next steps.
Standa Zivny
Title: On Relaxations of Satisfiability
Abstract: In this talk, I’ll report on recent results on two types of relaxations of satisfiability for combinatorial problems, namely satisfiability via operators for constraint satisfaction problems, and satisfiability with weaker constraints. A part of the talk is based on joint work with Andrei Bulatov (SFU).