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
Three C&O faculty win Outstanding Performance Awards
The awards are given each year to faculty members across the University of Waterloo who demonstrate excellence in teaching and research.
Prof. Alfred Menezes is named Fellow of the International Association for Cryptologic Research
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.
Events
URA Seminar - Thomas Lesgourgues
Title: On the use of senders in Ramsey Theory
Speaker: | Thomas Lesgourgus |
Affiliation: | University of Waterloo |
Location: | MC 5479 |
Abstract: In this talk I will introduce and investigate some parameters in Graph Ramsey theory, beyond the traditional Ramsey numbers. A crucial ingredient for their analysis is the existence of gadget graphs, called signal senders, that were initially developed by Burr, Erdős and Lovász in 1976. I will explain their origin, properties, and try to convey their surprising strength. Using probabilistic methods, we will see how to build such gadgets, and how to use them to prove some theorems, previously out of reach without these tools.
Graphs and Matroids - Bertrand Guenin
Title: A relaxation of Woodall’s conjecture
Speaker: | Bertrand Guenin |
Affiliation: | University of Waterloo |
Location: | MC 5479 |
Abstract: In a directed graph, a directed cut (dicut for short) is a cut where all arcs are directed from one shore to the other; a directed join (dijoin for short) is a set of arcs whose contraction makes the digraph strongly connected. The celebrated Lucchesi–Younger theorem states that for any directed graph the size of the smallest dijoin equals the maximum number of pairwise disjoint dicuts. Woodall’s conjecture posits that the size of the smallest dicut equals the maximum number of pairwise disjoint dijoins.
C&O Reading Group - Rian Neogi
Title: Bipartite Perfect Matching is in Quasi-NC, Part II
Speaker: | Rian Neogi |
Affiliation: | University of Waterloo |
Location: | MC 6029 |
Abstract: Mulmuley, Vazirani, and Vazirani gave a randomized parallel algorithm for checking whether a perfect matching exists in a graph. In doing so, they came up with the infamous isolation lemma, which found several uses in other areas of computer science. The isolation lemma is inherently randomized, and it has been a long-standing open problem to derandomize the lemma. In this talk, I will go over the breakthrough work of Fenner, Gurjar, and Thierauf where they almost completely derandomize the isolation lemma in the special case when applied to the bipartite perfect matching problem. In doing so, they give a deterministic parallel algorithm for perfect matching that uses a quasi-polynomial number of processors.