Events

Title: Follow the Regularized Leader and Mirror Descent

Abstract: In previous talks, we have seen how the multiplicative weights method and gradient descent solve the regret minimization problem. In this talk we will go over a meta-algorithm called Follow the Regularized Leader (FTRL). We will show how FTRL generalizes both multiplicative weights and gradient descent. We will also talk about the Mirror Descent meta-algorithm, and show its equivalence with FTRL.

Title: Combinatorial Action in Causal Set Quantum Gravity

Abstract: In this talk, I will first provide a brief overview of causal set theory, an approach to quantum gravity. This theory proposes that spacetime is fundamentally characterized by a partially ordered set (poset), in which the partial order represents causal relations and the number of elements signifies the volume of a spacetime manifold region. I will then discuss how efforts to find a discrete counterpart of the d'Alembertian operator on a poset led to the formulation of the causal set action S_BDG. This action is defined as a linear combination of the counts of various order intervals. Further analysis has shown that while KR posets are predominant in the number of posets of size n, the quantum dynamics imposed by S_BDG suppresses them for large n. Finally, I will propose a method to derive the combinatorial analogue of Einstein's field equations on posets.

Title: Regret bounds for FTRL and Mirror Descent

Abstract: In the previous talk, I introduced FTRL and Mirror Descent and showed how they generalize two well-known algorithms of Multiplicative Weights and Gradient Descent. In this talk, I will show that FTRL and Mirror Descent are in fact equivalent in the sense that they produce the same sequence of predictions. Moreover, I will go over some regret bounds for these algorithms, that will generalize the regret bounds we get for multiplicative weights and gradient descent.

Title: Laplacian State Transfer

Abstract: Let $X$ be a graph and let $E_1,\ldots,E_d$ be the spectral idempotents of its adjacency matrix. If $a$ and $b$ are vertices in $X$, they are \textsl{strongly cospectral} if $E_re_ae_a^TE_r = E_re_be_b^T$ for each $r$. This is a relation between the two density matrices $e_aa_a^T$ and $e_be_b^T$, and is a necessary condition for state transfer between pure states.

If $L$ is the Laplacian of a graph $X$ with $m$ edges, the matrix $(1/2m)L$ is positive semidefinite with trace one, thus it is a density matrix. We call it a \textsl{Laplacian state}. It is pure only if $X$ is an edge. We have been investigating transfer between Laplacian states in continuous quantum walks. We have extended the definition of strongly cospectral to this case, have obtained a number of results are about various forms of state transfer. My talk will be a report on this.

(This is joint work with Ada Chan, Qiuting Chen, Wanting Sun and Xiaohong Zhang.)

Title: Biased cliques

Abstract: A biased clique is a collection of cycles in a complete graph G so that no theta of G contains exactly two cycles in the collection. They have interesting connections to both matroids and groups; I will give a survey of some results on these objects.

Title: Vertex models for the product of a Schur and Demazure polynomial

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.

Abstract: Demazure atoms and characters are polynomials that each form a Z-basis for polynomials in n variables. The product of a Schur polynomial with a Demazure atom (resp. character) expands into a linear combination of Demazure atoms (resp. characters) with positive integer structure coefficients. There are known combinatorial rules that compute these coefficients using "skyline tableaux" given by Haglund, Luoto, Mason and Willigenburg. I have found alternative rules using the theory of integrable vertex models, inspired by a technique introduced by Zinn-Justin.

Title: Online Edge Coloring with Tree Recurrences

Abstract: We will talk about online edge coloring in the edge arrival model. The vertex set V is known, and each edge arrives one by one, where it has to be colored irrevocably immediately. I will present the results from Kulkarni, Liu, Sah, Sawhney and Tarnawski [STOC 2022] which gives an algorithm that colors the graph with (e/e-1 + o(1))\delta colors.

Title: Subconstituents of Drackns 

Abstract: For a distance-regular graph X and an arbitrary vertex v, we often find interesting structure in the subgraph of X induced on vertices at distance 2 from v.

For example:

Any strongly-regular graph with parameters (n,k,a,k/2) can be found at distance 2 from a vertex in a distance-regular graph of diameter 3.

Certain distance-regular graphs of diameter 3 can be found at distance 2 from a vertex in a Moore graph of girth 5.

These (and more) examples are known as second-subconstituents, and they can be studied using the Terwilliger (or subconstituent) algebra of X. I will discuss this theory in the case that X is a distance-regular antipodal cover of a complete graph (drackn). This setting generalizes the first example and includes the second.

I will describe some general techniques for studying the Terwilliger algebras of drackns and then restrict to drackns without triangles. In this setting I will explain how to compute the spectrum of the second-subconstituent of any triangle-free drackn, except possibly the second-subconstituent OF a second-subconstituent of a Moore graph of valency 57.

Title: Odd cycle transversal in P5-free graphs

Abstract: Odd cycle transversal is a fun computational problem, somewhere between colouring and independent set: we are (equivalently) looking for a bipartite induced subgraph of maximum weight. As one might expect, this is NP-hard; I will tell you how to solve this problem in polynomial time in P5-free graphs (and more). Joint work with Cece Henderson, Evelyne Smith-Roberge, and Rebecca Whitman.

Note: I am COVID-cautious and will bring masks for those willing to wear them. 

Title: More Martin and c2 details.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.  Please also come to the pre-seminar to discuss what sorts of snacks and refreshments we might want going forward.

Abstract:  I'm going to tell you more of the details behind my Martin polynomial work last year with Erik Panzer which led to the proof of the c2 completion conjecture. I will actually describe the key bijection that proves it all, say some things about the permanent invariant, and cover other details that there hadn't been time for in the colloquium level presentation of the result.