The C&O department has 36 faculty members and 60 graduate students. We are intensely research oriented and hold a strong international reputation in each of our six major areas:

- Algebraic combinatorics
- Combinatorial optimization
- Continuous optimization
- Cryptography
- Graph theory
- Quantum computing

Read more about the department's research to learn of our contributions to the world of mathematics!

## News

## Prof. Alfred Menezes is named Fellow of the International Association for Cryptologic Researc

The Fellows program, which was established in 2004, is awarded to no more than 0.25% of the IACR’s 3000 members each year and recognizes “outstanding IACR members for technical and professional contributions to cryptologic research.”

## C&O student Ava Pun receives Jessie W. H. Zou Memorial Award

She received the award in recognition of her research on simulating virtual training environments for autonomous vehicles, which she conducted at the start-up Waabi.

## Jeremy Chiwezer wins Governor General's Gold Medal

The Governor General’s Gold Medal is one of the highest student honours awarded by the University of Waterloo.

## Events

## Algebraic and Enumerative Combinatorics - Li Yu

**Title: **Integrable systems on the dual space of Lie algebras arising from log-canonical cluster structures

Speaker: |
Li Yu |

Affiliation: |
University of Toronto |

Location: |
MC 6029 |

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

**Abstract: **Let $(X, \{~,~\})$ be an (affine) Poisson variety. A log-canonical cluster structure on $X$ is a cluster structure on the coordinate ring of $X$ such that $\{\phi, \psi\} = \text{const} \cdot \phi \psi$ whenever $\phi, \psi$ are cluster variables which belong to the same cluster. When the Poisson bivector vanishes at some point $x \in X$, the tangent space $T_x X$ comes equipped with a Poisson bracket $\{~,~\}^{\text{lin}}$, the linearization of $\{~,~\}$. Given a function $\phi$ on $X$, we propose a way of linearizing it to get a function $\phi^{\text{lin}}$ on $T_x X$. Very often, when $\{\phi_1, \cdots, \phi_n\}$ is a cluster in a log-canonical cluster structure on $(X, \{~,~\})$, $\{\phi_1^{\text{lin}}, \cdots, \phi_n^{\text{lin}}\}$ is an integrable system on $(T_x X, \{~,~\}^{\text{lin}})$. We present two scenarios where this is the case.

## Tutte Colloquium - Akash Sengupta

**Title: **Sylvester-Gallai type configurations and Polynomial Identity Testing

Speaker: |
Akash Sengupta |

Affiliation: |
University of Waterloo |

Location: |
MC 5501 |

**Abstract: **The classical Sylvester-Gallai theorem in combinatorial geometry says the following:

If a finite set of points in the Euclidean plane has the property that the line joining any two points contains a third point from the set, then all the points must be collinear.

More generally, a Sylvester-Gallai (SG)-type configuration is a finite set of geometric objects with certain local dependencies. A remarkable phenomenon is that the local constraints give rise to global dimension bounds for linear SG-type configurations, and such results have found far reaching applications to complexity theory and coding theory. In particular, SG-type configurations have been extremely useful in applications to Polynomial Identity Testing (PIT), a central problem in algebraic complexity theory.

In this talk, we will discuss non-linear generalizations of SG-type configurations which consist of polynomials. We will discuss how uniform bounds on SG-configurations give rise to deterministic poly-time algorithms for the PIT problem. I’ll talk about results showing that these non-linear SG-type configurations are indeed low-dimensional as conjectured by Gupta in 2014. This is based on joint works with A. Garg, R. Oliveira and S. Peleg.

## C&O Special Seminar - Vijay Vazirani

**Title: **A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length - Part 1

Speaker: |
Vijay Vazirani |

Affiliation: |
University of California, Irvine |

Location: |
MC 5479 |

**Abstract: **It is well known that the proof of some prominent results in mathematics took a very long time --- decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed --- over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.

The new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.

The purpose of this two-talk-sequence is to rectify that shortcoming.