Mathematical Computer Science Seminar : Past Events
Past Seminars
The following seminars have already happened, you may instead view upcoming seminars in this series.
Sept. 17, 2018
Will Perkins :
3 p.m. in 427 SEO
Abstract
We improve the classic Chabauty-Shannon-Wyner lower bound on the kissing number of Euclidean space by a factor linear in the dimension. The proof is based on analyzing a "hard cap" model related to the hard core lattice gas from statistical physics. The proof technique also applies to sphere packings and to independent sets in triangle-free graphs. I will use the connection with independent sets in graphs to describe some plausible scenarios for the densest sphere packings and kissing configurations in high dimensions. Based on joint work with Matthew Jenssen and Felix Joos.
Oct. 8, 2018
Peter Erdos :
3 p.m. in 427 SEO
Abstract
How to analyze real life networks? There are myriads of them and
usually experiments cannot be performed directly. Instead, scientists define
models, fix parameters and imagine the dynamics of evolution.
Then, they build synthetic networks on this basis (one, several, all)
and they want to sample them. However, there are far too many such networks.
Therefore, typically, some probabilistic method is used for sampling.
We will survey one such approach, the Markov Chain Monte Carlo method, to
sample realizations of given degree sequences. Some new results will be
discussed.
Oct. 15, 2018
Hemanshu Kaul :
3 p.m. in 427 SEO
Abstract
The list chromatic number of the Cartesian product of graphs is not well understood. The best result is by Borowiecki, Jendrol, Kral, & Miskuf (2006) who proved that the list chromatic number of the Cartesian product of two graphs can be bounded in terms of the list chromatic number and the coloring number of the factors, implying a bound exponential in the list chromatic number of the factors.
We show how the knowledge of the list color function (list coloring analogue of the chromatic polynomial) can be applied to list coloring of Cartesian products. We introduce the notion of strongly chromatic choosable graphs, that includes odd cycles, cliques, many more infinite families of graphs, and the join of a clique with any other such graph, as a notion of color-criticality in the context of chromatic-choosability. This leads to improved bounds on choosability of Cartesian product of certain large classes of graphs and to classes of chromatic-choosable Cartesian products of graphs. This is joint work with Jeffrey Mudrock.
Oct. 29, 2018
David Galvin :
3 p.m. in 427 SEO
Abstract
Many combinatorial matrices --- such as those of binomial coefficients, Stirling numbers of both kinds, and Lah numbers --- are known to be totally non-negative, meaning that all minors (determinants of square submatrices) are non-negative.
The examples noted above can be placed in a common framework: for each one there is a non-decreasing sequence $(a_1, a_2, \ldots)$, and a sequence $(e_1, e_2, \ldots)$, such that the $(m, k)$-entry of the matrix is the coefficient of the polynomial $(x - a_1) \cdots (x-a_k)$ in the expansion of $(x -e_1) \cdots (x - e_m)$ as a linear combination of the polynomials $1, x-a_1, \ldots, (x-a_1) \cdots (x-a_m)$.
I'll discuss this general framework, and for a non-decreasing sequence $(a_1, a_2, \ldots)$ sketch the proof of necessary and sufficient conditions on the sequence $(e_1, e_2,\ldots)$ for the corresponding matrix to be totally non-negative. I'll derive as corollaries the totally non-negativity of matrices of rook numbers of Ferrers boards, and of a family of matrices associated with chordal graphs.
Nov. 5, 2018
Steve Hanneke :
3 p.m. in 427 SEO
Abstract
In many machine learning applications, the effort required to manually
label the massive data sets necessary to train machine learning
systems to a high accuracy presents a major hurdle. One promising
approach to reducing the required training sample size is active
learning, a technique in which the learning algorithm participates in
interactively selecting examples to be labeled for training, in order
to focus the human expert's efforts on labeling only informative and
non-redundant examples. Active learning holds great potential for
dramatically reducing the number of labeled training examples needed
for learning. However, despite decades of research on the subject, the
most popular active learning algorithms in the applications literature
are known to be unreliable and sensitive to violations of modeling
assumptions, which has held back the widespread applicability of
active learning in practice. At the root of this problem, it seems we
have lacked a complete understanding of the basic principles that
should underlie the design of good active learning algorithms. Such a
situation calls for a careful theoretical approach to the problem.
In this talk, I will articulate essential principles for the design of
effective active learning algorithms, distilled from over a decade of
research on the theory of active learning. Moreover, I will describe a
general active learning strategy based on these principles, which is
provably near-optimal, in the sense that the number of labeled
training examples sufficient to achieve a given accuracy guarantee
cannot be significantly reduced by any other active learning
algorithm. In the process, I will discuss the fundamental trade-offs
and general complexity measures intrinsic to the active learning
setting, and present formulas expressing the minimum number of labeled
examples sufficient and necessary for an optimal active learning
algorithm to achieve a given accuracy guarantee.
Nov. 12, 2018
Ruth Luo :
3 p.m. in 427 SEO
Abstract
We will talk about a generalization of the Tur\'an problem for hypergraphs: given a graph $F$, what is the maximum number of hyperedges an $r$-uniform $n$-vertex Berge $F$-free hypergraph can have? In particular, we will discuss tools used to reduce the hypergraph problem to problems for graphs. Finally, I will present some recent results for graphs without long Berge cycles. This is joint work with (different subsets of) Zoltan Furedi and Alexandr Kostochka.
Dec. 3, 2018
Matthew Jenssen :
4 p.m. in 427 SEO
Abstract
We give an FPTAS and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) d-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the non-uniqueness regime of the infinite d-regular tree. Joint work with Peter Keevash and Will Perkins.
March 5, 2019
Hunter Chase :
1 p.m. in 427 SEO
Abstract
Several notions of combinatorial complexity of set systems correspond with
both model-theoretic dividing lines and notions of machine learning.
We extend these parallels to learning with equivalence queries.
The relevant measures are the consistency dimension and
strong consistency dimension, which roughly correspond to NFCP formulas.
We use these along with Littlestone dimension to obtain new bounds on
several variants of equivalence query learning.
April 8, 2019
Andrew Suk :
3 p.m. in 427 SEO
Abstract
The Ramsey number R(p; m) is the smallest integer n such
that any m-coloring on the edges of the complete n-vertex graph
contains a monochromatic copy of K_p. Here, we think of p as a fixed
constant, and m tends to infinity. In his work related to Fermat’s
Last Theorem, Schur proved that
2^Ω(m) < R(3;m) < O(m!).
While small improvements have been made to the lower bound, the upper
bound remains unchanged. It is an old problem of Erdős to decide
whether R(p; m) = 2^O(m), when p is fixed. In this talk, I will sketch
a proof of this if we further assume that the edge colorings are
semi-algebraic with bounded complexity. This is joint work with Jacob
Fox and Janos Pach.
April 15, 2019
Balazs Szorenyi :
3 p.m. in 427 SEO
Abstract
Stochastic approximation (SA) algorithms are sequential stochastic update rules for finding zeros of a function for which only noisy access is available. Due to their easy applicability and natural fit to optimization problems, SA methods have become a fundamental paradigm in various fields. The underlying theory is particularly important in reinforcement learning, where it can be used to analyze the behavior of an agent's policy.
In this talk, I would like to present some recent advancements on showing finite time bounds for the problem, and discuss their relation to some basic reinforcement learning algorithms.
April 22, 2019
Samantha Petti :
3 p.m. in 427 SEO
Abstract
In this talk we introduce two different random graph models that produce sparse graphs with overlapping community structure and discuss community detection in each context. The Random Overlapping Community (ROC) model produces a sparse graph by constructing many Erdos Renyi random graphs (communities) on small randomly selected subsets of vertices. By varying the size and density of these communities, ROC graphs can be tuned to exhibit a wide range normalized of closed walk count vectors, including those of hypercubes. This is joint work with Santosh Vempala. In the second half of the talk, we introduce the Community Configuration Model (CCM), a variant of the configuration model in which half-edges are assigned colors and pair according to a matching rule on the colors. The model is a generalization of models in the statistical physics literature and is a natural finite analog for classes of graphexes. We describe a hypothesis testing algorithm that determines whether a graph came from a community configuration model or a traditional configuration model. This is joint work with Christian Borgs, Jennifer Chayes, Souvik Dhara, and Subhabrata Sen.
April 29, 2019
Andrzej Dudek :
3 p.m. in 427 SEO
Abstract
It follows from the theorems of Dirac and of Koml\'os, Sark\"ozy, and Szemer\'edi, who
confirmed the Pos\'a-Seymour conjecture, that for every $k\ge 1$
and sufficiently large $n$ already the minimum degree $\delta(G) \ge \frac{k}{k+1} n$
for an $n$-vertex graph $G$ alone suffices to ensure the existence of the $k$-th power of a Hamiltonian cycle.
In this talk we will determine the number of random edges one has to add to a graph $G$ with minimum degree $\delta(G) \ge \left(\frac{k}{k+1} +\varepsilon\right)n$ (with $\varepsilon>0$) in order to create an $\ell$-th power of a Hamiltonian cycle, where $\ell\ge k+1$.
This is joint work with Sylwia Antoniuk, Christian Reiher, Andrzej Ruci\'nski and Mathias Schacht.
Sept. 22, 2025
Haoran Luo :
3 p.m. in 1227 SEO
Abstract
The Erdős–Rogers function f_{K_s, K_t}(n) is defined as the minimum possible value of the s-independence number over all n-vertex K_t -free graphs. Introduced by Erdős and Rogers in 1962, it has since become an important topic in Ramsey theory, with numerous papers achieving significant improvements on the bounds for various pairs (s, t). In this talk, we will discuss two recent generalizations of the Erdős–Rogers function: the multicolor case and the case of arbitrary pairs of graphs. We will also present some open problems.
Oct. 6, 2025
Dhruv Mubayi :
3 p.m. in 1227 SEO
Abstract
We consider the following general question that encompasses some of the most celebrated theorems in Combinatorics.
Given a small graph H and a large graph G with density x, what is the possible number of induced subgraphs of G that are isomorphic to H.
A complete answer is known only in the case when H is a clique or a two edge star (and their complements). We will discuss some general theory around this problem and then focus on some specific H. This is joint work with Xizhi Liu and Christian Reiher.
Nov. 3, 2025
Caroline Terry :
3 p.m. in 1227 SEO
Abstract
We begin by presenting work of the author and Julia Wolf from 2021 showing that any subset of an elementary abelian $p$-group of bounded VC_2-dimension is well approximated by a union of atoms of a quadratic factor of bounded complexity. This result relies on a general quadratic arithmetic regularity lemma of Green and Tao, and consequently, yields bounds on the linear and quadratic complexities of the factor which are of tower-type in $\varepsilon^{-1}$, where $\varepsilon$ is the approximation parameter. We then present more recent work, also joint with Julia Wolf, which shows the bound on the quadratic complexity of the factor appearing in the structure theorem for sets of bounded VC_2-dimension can improved drastically, specifically to a logarithm in a power of $\varepsilon^{-1}$.
Dec. 1, 2025
Gyorgy Turan :
3 p.m. in 1227 SEO
Abstract
Large language models (LLM) have impressive performance on hard tasks, but also exhibit brittleness in simple tasks. We describe an experiment on a basic ``sub-reasoning'' task: deciding if an element belongs to a set. The results give a comprehensive picture of the various types of errors that can occur.
In the second part of the talk we give a brief overview of the mathematical challenges posed by the goal of understanding how a neural network works, including understanding what an LLM ``knows''.
Joint work with Gabor Berend, Lea Hergert, Mark Jelasity and Mario Szegedy.
March 2, 2026
Dingding Dong :
3 p.m. in 1227 SEO
Abstract
We say that a graph $G$ is $(k,l)$-stable if removing $k$ vertices from it reduces its
independence number by at most $l$. We say that $G$ is tight $(k,l)$-stable if it is
$(k,l)$-stable and its independence number equals $\lfloor(n-k+1)/2\rfloor+l$, the
maximum possible, where $n$ is the vertex number of $G$. Answering a question of
Dong and Wu, we show that every tight $(2,0)$-stable graph with odd vertex number
must be an odd cycle. Moreover, we show that for all $k \ge 3$, every tight
$(k,0)$-stable graph has at most $k+6$ vertices. This is joint work with Sammy Luo.
March 16, 2026
David James :
3 p.m. in 1227 SEO
Abstract
A weighted hypergraph G is (F, r)-free if any copy of F in G has weight less than r. The weighted Turán number is the maximum weight of an (F, r)-free hypergraph on n vertices. Let H be the 3-graph {abc, abd, cde}. In a paper of Keevash and Mubayi, the asymptotic behavior, exact results for large n, and stability theorems of H-free hypergraphs are proven. We generalize all such results to (H, r)-free weighted hypergraphs for all values of r. These are the first such results for hypergraphs.
April 13, 2026
Dylan King :
3 p.m. in 1227 SEO
Abstract
The triangle Ramsey number R(3,k) is the smallest n such that any n-vertex graph contains either a triangle or an independent set of size k. Through the hard work of many researchers, around 30 years ago the order of magnitude of R(3,k) was determined to be k^2/log(k), and the correct leading constant is now of serious interest. The main result of this talk improves the best known lower bound on this constant from 1/2 to 1/3, using a flexible construction.
Based on joint work with Zion Hefty, Paul Horn, and Florian Pfender.
April 27, 2026
Thuy-Duong (June) Vuong :
3 p.m. in 1227 SEO
Abstract
We study the problem of approximating the partition function of the transverse-field Ising model (TFIM), a widely studied quantum many-body model with important applications in quantum simulation and quantum annealing. Despite its fundamental importance, the algorithmic landscape for computing the TFIM partition function has remained poorly understood beyond restricted parameter regimes. We provide a precise characterization of the temperature regimes in which efficient approximation is possible, establishing a sharp computational phase transition. Let $J$ denote the symmetric interaction matrix and $\Delta(J) = \lambda_{\max}(J)-\lambda_{\min}(J)$ denote its spectral width. We show that, for all inverse temperatures $\beta \in [0,1/\Delta(J)]$, there exists an efficient classical randomized algorithm that approximates the partition function $\text{tr}(e^{-\beta H})$ to within an arbitrarily small multiplicative factor. To obtain this result, we apply the standard Trotter decomposition to map the quantum model to a classical spin system, and then leverage new techniques in Markov chain analysis to derive an efficient algorithm that samples from and computes the partition function of the resulting distribution. This temperature threshold is tight: for $\beta > 1/\Delta(J)$, we show that approximating the partition function, even within an exponential factor, is NP-hard and thus is unlikely to admit an efficient classical or quantum algorithm.
Joint work with Alistair Sinclair.