## University COVID-19 update

### Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

# Events - 2021

Friday, June 25, 2021 — 3:30 PM EDT

## Tutte Colloquium - Dmitriy Drusvyatskiy

Title: From low probability to high confidence in stochastic convex optimization

 Speaker: Dmitriy Drusvyatskiy Affliliation: University of Washington Zoom: Contact Emma Watson

Abstract:

Standard results in stochastic convex optimization bound the number of samples that an algorithm needs to generate a point with small function value in expectation. More nuanced high probability guarantees are rare, and typically either rely on “light-tail” noise assumptions or exhibit worse sample complexity. In this work, we show that a wide class of stochastic optimization algorithms can be augmented with high confidence bounds at an overhead cost that is only logarithmic in the confidence level and polylogarithmic in the condition number.

Thursday, June 24, 2021 — 1:00 PM EDT

## Algebraic Combinatorics Seminar - Terrence George

Title: Arctic curves for groves

 Speaker: Terrence George Affiliation: University of Michigan Zoom: Contact Stephen Melczer

Abstract:

The limit shape phenomenon is a "law of large numbers" for random surfaces: the random surface looks macroscopically like the "average surface". The first result of this kind was the celebrated arctic circle theorem for domino tilings of the aztec diamond. The limit shape has macroscopic regions with different qualitative behavior, and the arctic curve is the boundary separating these regions.

Monday, June 21, 2021 — 11:30 AM EDT

## Algebraic Graph Theory Seminar - Paula Kimmerling

Title: Average Mixing Matrices of Trees and Stars

 Speaker: Paula Kimmerling Affiliation: Washington State University Zoom: Contact Soffia Arnadottir

Abstract:

We define the average mixing matrix (AMM) of a continuous-time quantum walk on a graph using the orthogonal projections onto the eigenspaces of the adjacency matrix A. From there, one of the properties that has been studied is the rank of the AMM. This is easiest to do if the eigenvalues of A are simple, and we’ll review some of the results on this from Coutinho et. al. (2018).

Friday, June 18, 2021 — 3:30 PM EDT

## Tutte Colloquium - Marni Mishna

Title: Lattice Walk Enumeration: Analytic, algebraic and geometric aspects

 Speaker: Marni Mishna Affliliation: Simon Fraser University Zoom: Contact Emma Watson

Abstract:

This talk will examine the rich topic of lattice path enumeration. A very classic object of combinatorics, lattice walks withstand study from a variety of perspectives. Even the simple task of classifying the two dimensional walks restricted to the first quadrant has brought into play a surprising diversity of techniques from algebra to analysis to geometry. We will consider walks under a few different lenses.

Friday, June 18, 2021 — 11:30 AM EDT

## Algebraic Graph Theory Seminar - Dheer Noal Desai

Title: The spectral radius of graphs with no odd wheels

 Speaker: Dheer Noal Desai Affiliation: University of Delaware Zoom: Contact Soffia Arnadottir

Abstract:

The odd wheel W_{2k+1} is the graph formed by joining a vertex to a cycle of length 2k. In this talk, we will investigate the largest value of the spectral radius of the adjacency matrix of an n-vertex graph that does not contain W_{2k+1}.

Thursday, June 17, 2021 — 1:00 PM EDT

## Algebraic Combinatorics Seminar - Angèle Hamel

Title: Identities for ninth variation Schur Q-functions

 Speaker: Angèle Hamel Affiliation: Wilfrid Laurier University Zoom: Contact Stephen Melczer

Abstract:

Recently Okada defined algebraically ninth variation skew Q-functions, in parallel to Macdonald's ninth variation skew Schur functions. Here we introduce a skew shifted tableaux definition of these ninth variation skew Q-functions, and prove by means of a non-intersecting lattice path model a Pfaffian outside decomposition result in the form of a ninth variation version of Hamel's Pfaffian outside decomposition identity.

Friday, June 11, 2021 — 3:30 PM EDT

## Tutte Colloquium - Cécile Pierrot

Title: The discrete logarithm problem in finite fields

 Speaker: Cécile Pierrot Affliliation: French National Institute for Computer Science Research (INRIA) Zoom: Contact Emma Watson

Abstract:

The security of currently deployed public key protocols relies on the presumed hardness of problems often coming from number theory, such as factoring a large integer or solving the discrete logarithm problem in some group.

In this talk we focus on discrete logarithms in finite fields. We explain what is a discrete logarithm, why cryptographers need them, and we focus then on algorithms to solve the related problem, together with open questions in this area.

Thursday, June 10, 2021 — 4:00 PM EDT

## Joint Colloquium - Shayla Redlin

Title: Counting Antichains in the Boolean Lattice

 Speaker: Shayla Redlin Affiliation: University of Waterloo Zoom: Contact Maxwell Levit

Abstract:

How many antichains are there in the Boolean lattice P(n)? Sperner's theorem (1928) tells us that the largest antichain in P(n) has size A = (n choose n/2). A subset of an antichain is an antichain, so there are at least 2^A antichains in P(n). Interestingly, it turns out that this is close to the total, as Kleitman (1969) showed that the number of antichains is 2^(A(1+x)) where x goes to zero as n goes to infinity.

Thursday, June 10, 2021 — 1:00 PM EDT

## Algebraic Combinatorics Seminar - Lukas Nabergall

Title: Enumerating hereditary classes of chord diagrams

 Speaker: Lukas Nabergall Affiliation: University of Waterloo Zoom: Contact Stephen Melczer

Abstract:

A class of combinatorial structures is hereditary if membership in the class is closed under taking substructures. Hereditary classes have been extensively studied for a variety of objects, notably graphs and permutations. A central problem is to determine the number of objects of size n in a given hereditary class. We discuss this problem for chord diagrams, perfect matchings of [2n].

Friday, June 4, 2021 — 3:30 PM EDT

## Tutte Colloquium - Kanstantsin Pashkovich

Title: On the approximability of the maximum cardinality stable matching problem with ties

 Speaker: Kanstantsin Pashkovich Affliliation: University of Waterloo Zoom: Contact Emma Watson

Abstract:

The maximum cardinality stable matching problem is central in game theory. When participants are allowed to have ties in their preferences, the problem of finding a stable matching of maximum cardinality is NP-hard, even when the ties are of size two. Moreover, in this setting it is UGC-hard to provide an approximation for the maximum cardinality stable matching problem with a constant factor smaller than 4/3.

Thursday, June 3, 2021 — 1:00 PM EDT

## Algebraic Combinatorics Seminar - Oliver Pechenik

Title: What is the degree of a Grothendieck polynomial?

 Speaker: Oliver Pechenik Affiliation: University of Waterloo Zoom: Contact Stephen Melczer

Abstract:

Jenna Rajchgot observed that the Castelnuovo-Mumford regularity of matrix Schubert varieties is computed by the degrees of the corresponding Grothendieck polynomials. We give a formula for these degrees.

Monday, May 31, 2021 — 11:30 AM EDT

## Algebraic Graph Theory Seminar - Jo Ellis-Monaghan

Title: An algebraic framework for twualities of embedded graphs

 Speaker: Jo Ellis-Monaghan Affiliation: Korteweg-de Vries Instituut voor Wiskunde, Universiteit van Amsterdam Zoom: Contact Soffia Arnadottir

Abstract:

We develop algebraic tools to identify and generate new surface embeddings of graphs with various forms of self-twuality including geometric duality, Petrie duality, Wilson duality, and both forms of triality (which is like duality, but of order three instead of two).  These operations are of particular interest because of their interplay with graph symmetries and graph polynomials.

Friday, May 28, 2021 — 3:30 PM EDT

## Tutte Colloquium - Jon Yard

Title: Algebraic formulations of Zauner's conjecture

 Speaker: Jon Yard Affliliation: University of Waterloo Zoom: Contact Emma Watson

Abstract:

Tight complex projective 2-designs are simultaneously maximal sets of equiangular lines and minimal complex projective 2-designs. In quantum information theory, they define optimal measurements known as SIC-POVMs (Symmetric Informationally Complete Positive Operator-Valued Measures).  They are conjectured by Zauner to exist in every dimension, even as specific group orbits.

Friday, May 21, 2021 — 3:30 PM EDT

## Tutte Colloquium - Steve Melczer

Title: Positivity Problems for Linear Recurrences

 Speaker: Steve Melczer Affliliation: University of Waterloo Zoom: Contact Emma Watson

Abstract:

Although sequences satisfying linear recurrence relations have been studied for centuries, and appear as some of the first examples of combinatorial sequences encountered in an introductory combinatorics class, there are natural examples of simply stated problems related to their basic behaviour whose decidability is unknown. In this talk we survey some open computability and complexity questions related to the positivity of linearly recurrent sequences, before examining a new approach to proving positivity using rigorous numerical methods for functions satisfying linear differential equations.

Thursday, May 20, 2021 — 1:00 PM EDT

## Algebraic Combinatorics Seminar - Steven Karp

Title: q-Whittaker functions, finite fields, and Jordan forms

 Speaker: Steven Karp Affiliation: UQAM Zoom: Contact Steve Melczer

Abstract:

The q-Whittaker symmetric function associated to an integer partition is a q-analogue of the Schur symmetric function. We give a new formula for the q-Whittaker function in terms of partial flags compatible with a nilpotent endomorphism over the finite field of size 1/q.

Monday, May 17, 2021 — 11:30 PM EDT

## Algebraic Graph Theory Seminar - Bojen Mohar

Title: Minimum eigenvalue of nonbipartite graphs

 Speaker: Bojan Mohar Affiliation: Simon Fraser University Zoom: Contact Soffia Arnadottir

Abstract:

Let \rho and \lambda be the largest and the smallest eigenvalue of a connected graph G. It is well-known that \rho + \lambda \geq 0 and that equality occurs if and only if G is bipartite. The speaker will discuss what else can we say when G is not bipartite.

Friday, May 14, 2021 — 3:30 PM EDT

## Tutte Colloquium - Hao Huang

Title: Interlacing methods in Extremal Combinatorics

 Speaker: Hao Huang Affliliation: Emory University Zoom: Contact Emma Watson

Abstract:

Extremal Combinatorics studies how large or how small a collection of finite objects could be, if it must satisfy certain restrictions. In this talk, we will discuss applications of spectral graph theory, more specifically eigenvalue interlacing, to prove various interesting results in Extremal Combinatorics. We will discuss the Erdos-Ko-Rado Theorem and its degree version, an isodiametric inequality for discrete cubes, and the resolution of a thirty-year-old open problem in Theoretical Computer Science, the Sensitivity Conjecture of Nisan and Szegedy. Several open problems will also be mentioned during this talk.

Monday, May 10, 2021 — 11:30 AM EDT

## Algebraic Graph Theory Seminar - Mariia Sobchuk

Title: Quantum independence number

 Speaker: Mariia Sobchuk Affiliation: University of Waterloo Zoom: Contact Soffia Arnadottir

Abstract:

From this talk you will be able to learn what quantum independence number is and how it is different from the classical independence number. I will provide both known individual and infinite families of the graphs where classical and quantum independent numbers are different, as well as some of our generalisations of these examples.

Monday, April 26, 2021 — 11:30 AM EDT

## Algebraic Graph Theory Seminar - Sabrina Lato

Title: A Spectral Moore Bound for Bipartite Semiregular Graphs

 Speaker: Sabrina Lato Affiliation: University of Waterloo Zoom: Contact Soffia Arnadottir

Abstract:

The Moore bound provides an upper bound on the number of vertices of a regular graph with a given degree and diameter, though there are disappointingly few graphs that achieve this bound. Thus, it is interesting to ask what additional information can be used to give Moore-type bounds that are tight for a larger number of graphs. Cioaba, Koolen, Nozaki, and Vermette considered regular graphs with a given second-largest eigenvalue, and found an upper bound for such graphs.

Friday, April 23, 2021 — 3:30 PM EDT

## Tutte Colloquium - Hao Hu

Title: Robust Interior Point Methods for Key Rate Computation in Quantum Key Distribution

 Speaker: Hao Hu Affliliation: University of Waterloo Zoom: Contact Emma Watson

Abstract:

We study semidefinite programs for computing the key rate in finite dimensional quantum key distribution (QKD) problems. Through facial reduction, we derive a semidefinite program which is robust and stable in the numerical computation. Our program avoids the difficulties for current algorithms from singularities that arise due to loss of positive definiteness. This allows for the derivation of an efficient Gauss-Newton interior point approach. We provide provable lower and upper bounds for the hard nonlinear semidefinite programming problem.

Monday, April 19, 2021 — 11:03 AM EDT

## Algebraic Graph Theory Seminar - Julien Sorci

Title: Quantum walks on Cayley graphs

 Speaker: Julien Sorci Affiliation: University of Florida Zoom: Contact Soffia Arnadottir

Abstract:

In this talk we will look at the continuous-time quantum walk on Cayley graphs of finite groups. We will show that normal Cayley graphs enjoy several nice algebraic properties, and then look at state transfer phenomena in Cayley graphs of certain non-abelian p-groups called the extraspecial p-groups. Some of the results we present are part of joint work with Peter Sin.

Friday, April 16, 2021 — 3:30 PM EDT

## Tutte Colloquium - Tom Kelly

Title: A proof of the Erdős–Faber–Lovász conjecture

 Speaker: Tom Kelly Affliliation: University of Birmingham Zoom: Contact Emma Watson

Abstract:

The Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$.  We prove this conjecture for every sufficiently large $n$.  This is joint work with Dong Yeap Kang, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.

Thursday, April 15, 2021 — 1:00 PM EDT

## Algebraic Combinatorics Seminar - Yannic Vargas

Title: Algebraic structure of the Hopf algebra of double posets

 Speaker: Yannic Vargas Affiliation: Potsdam University Zoom: Contact Karen Yeats

Abstract:

A Hopf algebra of double posets was introduced by Claudia Malvenuto and Christophe Reutenauer in 2011, motivated by the study of pictures of tableaux as defined by Zelevinsky. Starting from the correspondence between top-cones in the braid arrangement and partial orders, we investigate several properties of the Hopf algebra of double posets as the image of a Hopf monoid (via the Fock functor). In particular, we obtain a non-cancellative formula for the antipode. A description of the primitive space is also discussed.

Monday, April 12, 2021 — 11:30 AM EDT

## Algebraic Graph Theory Seminar - Karen Yeats

Title: Feynman integrals as algebraic graph theory

 Speaker: Karen Yeats Affiliation: University of Waterloo Zoom: Contact Soffia Arnadottir

Abstract:

I will overview how Feynman integrals should feel very familiar to algebraic graph theorists, and then say a few words about current directions of interest to me, particularly the c_2 invariant.

Friday, April 9, 2021 — 3:30 PM EDT

## Tutte Colloquium - Alicia Kollár

Title: Circuit QED Lattices: Synthetic Quantum Systems on Line Graphs

 Speaker: Alicia Kollár Affliliation: University of Maryland Zoom: Contact Emma Watson

Abstract:

After two decades of development, superconducting circuits have emerged as a rich platform for quantum computation and simulation. Lattices of coplanar waveguide (CPW) resonators realize artificial photonic materials or photon-mediated spin models. Here I will highlight the special property that these lattice sites are deformable and allow for the implementation of devices with graph-like configurational flexibility. In particular, I will show that it is possible to create synthetic materials in which microwave photons experience negative curvature, which is impossible in conventional electronic materials [1].

## Pages

### June 2021

S M T W T F S
30
31
1
2
5
6
7
8
9
12
13
14
15
16
19
20
22
23
26
27
28
29
30
1
2
3
1. 2021 (58)
1. June (11)
2. May (7)
3. April (9)
4. March (13)
5. February (8)
6. January (10)
2. 2020 (119)
1. December (5)
2. November (12)
3. October (12)
4. September (12)
5. August (11)
6. July (17)
7. June (11)
8. May (6)
9. March (11)
10. February (11)
11. January (11)
3. 2019 (167)
4. 2018 (136)
5. 2017 (103)
6. 2016 (137)
7. 2015 (136)
8. 2014 (88)
9. 2013 (48)
10. 2012 (39)
11. 2011 (36)
12. 2010 (40)
13. 2009 (40)
14. 2008 (39)
15. 2007 (15)