Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 5198884567, ext 33038
PDF files require Adobe Acrobat Reader.
Visit our COVID19 information website to learn how Warriors protect Warriors.
Please note: The University of Waterloo is closed for all events until further notice.
Sun  Mon  Tue  Wed  Thu  Fri  Sat 

30

31

1

2

5








6

7

8

9

12








13

14

15

16

19








20

22

23

26







27

29

30

1

2

3








Title: What is the degree of a Grothendieck polynomial?
Speaker: Oliver Pechenik Affiliation: University of Waterloo Zoom: Contact Stephen MelczerAbstract:
Jenna Rajchgot observed that the CastelnuovoMumford regularity of matrix Schubert varieties is computed by the degrees of the corresponding Grothendieck polynomials. We give a formula for these degrees.
Title: On the approximability of the maximum cardinality stable matching problem with ties
Speaker: Kanstantsin Pashkovich Affliliation: University of Waterloo Zoom: Contact Emma WatsonAbstract:
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 NPhard, even when the ties are of size two. Moreover, in this setting it is UGChard to provide an approximation for the maximum cardinality stable matching problem with a constant factor smaller than 4/3.
Title: Enumerating hereditary classes of chord diagrams
Speaker: Lukas Nabergall Affiliation: University of Waterloo Zoom: Contact Stephen MelczerAbstract:
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].
Title: Counting Antichains in the Boolean Lattice
Speaker: Shayla Redlin Affiliation: University of Waterloo Zoom: Contact Maxwell LevitAbstract:
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.
Title: The discrete logarithm problem in finite fields
Speaker: Cécile Pierrot Affliliation: French National Institute for Computer Science Research (INRIA) Zoom: Contact Emma WatsonAbstract:
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.
Title: Identities for ninth variation Schur Qfunctions
Speaker: Angèle Hamel Affiliation: Wilfrid Laurier University Zoom: Contact Stephen MelczerAbstract:
Recently Okada defined algebraically ninth variation skew Qfunctions, in parallel to Macdonald's ninth variation skew Schur functions. Here we introduce a skew shifted tableaux definition of these ninth variation skew Qfunctions, and prove by means of a nonintersecting lattice path model a Pfaffian outside decomposition result in the form of a ninth variation version of Hamel's Pfaffian outside decomposition identity.
Title: The spectral radius of graphs with no odd wheels
Speaker: Dheer Noal Desai Affiliation: University of Delaware Zoom: Contact Soffia ArnadottirAbstract:
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 nvertex graph that does not contain W_{2k+1}.
Title: Lattice Walk Enumeration: Analytic, algebraic and geometric aspects
Speaker: Marni Mishna Affliliation: Simon Fraser University Zoom: Contact Emma WatsonAbstract:
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.
Title: Average Mixing Matrices of Trees and Stars
Speaker: Paula Kimmerling Affiliation: Washington State University Zoom: Contact Soffia ArnadottirAbstract:
We define the average mixing matrix (AMM) of a continuoustime 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).
Title: Arctic curves for groves
Speaker: Terrence George Affiliation: University of Michigan Zoom: Contact Stephen MelczerAbstract:
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.
Title: From low probability to high confidence in stochastic convex optimization
Speaker: Dmitriy Drusvyatskiy Affliliation: University of Washington Zoom: Contact Emma WatsonAbstract:
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 “lighttail” 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.
Title: State transfer for paths with weighted loops at the end vertices
Speaker: Steve Kirkland Affiliation: University of Manitoba Zoom: Contact Soffia ArnadottirAbstract:
We consider a continuous time quantum walk on an unweighted path on n vertices, to which a loop of weight w has been added at each end vertex. Let f(t) denote the fidelity of state transfer from one end vertex to the other at time t. In this talk we give upper and lower bounds on f(t) in terms of w, n and t; further, given a > 0 we discuss the values of t for which f(t) > 1a.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 5198884567, ext 33038
PDF files require Adobe Acrobat Reader.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Indigenous Initiatives Office.