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 Combinatorics and Optimization graduate students receive $120,000 as part of the federal government’s CRTAS program
Current Combinatorics and Optimization PhD students Cece Henderson, Nic Swanson and Ben Wong each received a Canada Graduate Research Scholarship – Doctoral (CGRS D). Valued at $40,000 per year, the scholarship runs for three years.
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.
Sina Kalantarzadeh 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
CombOpt Reading Group | Mehrdad Sohrabi, Approximating graphic TSP by b-matchings
| Speaker: |
Mehrdad Sohrabi |
| Affiliation: | University of Waterloo |
| Room: | MC 6029 |
Abstract: We are going to talk about approximating graphic TSP, which is a variant of TSP where the distances come from shortest paths between vertices of an undirected graph. We will talk about Mömke and Svensson’s approach, which used matchings to improve the approximation ratio, and also our recent generalization that uses b-matchings. This is joint work with Levent Tunçel and Swati Gupta.
Graphs and Matroids | Cece Henderson, On the Hypergraph Nash-Williams' Conjecture
| Speaker: | Cece Henderson |
| Affiliation: | University of Waterloo |
| Room: | MC 6029 |
Abstract: The study of combinatorial designs includes some of the oldest questions at the heart of combinatorics. In a breakthrough result of 2014, Keevash proved the longstanding Existence Conjecture by showing the existence of (n,q,r)-Steiner systems (equivalently K_q^r-decompositions of K_n^r) for all large enough n satisfying the necessary divisibility conditions. Meanwhile, in recent decades, incremental progress has been made on the celebrated Nash-Williams' Conjecture of 1970, which posits that any large enough, triangle-divisible graph on n vertices with minimum degree at least 3n/4 admits a triangle decomposition. In 2021, Glock, Kühn, and Osthus proposed a generalization of these results by conjecturing a hypergraph version of the Nash-Williams' Conjecture, where their proposed minimum degree K_q^r-decomposition threshold is motivated by hypergraph Turán theory. By using the recently developed method of refined absorption and establishing a non-uniform Turán theory, we tie the K_q^r-decomposition threshold to its fractional relaxation. Combined with the best-known fractional decomposition threshold from Delcourt, Lesgourgues, and Postle, this dramatically closes the gap between what was known and the above conjecture. This talk is based on joint work with Luke Postle.
Crypto Reading Group on quantum computing | Jonas Janneck & Camryn Steckel, The Quantum-Accessible Random Oracle Model
| Speaker: | Jonas Janneck & Camryn Steckel |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract: A lot of classical constructions are proven secure the random oracle model. With quantum adversaries, it is necessary to consider a quantum-accessible model allowing the adversary to query the oracle with quantum states. In this talk, we define such an oracle and show its implications on classical security proofs. We will present an example separating the classical and quantum-accessible random oracle models using a scheme that is secure when the adversary is given classical access to the random oracle, but is insecure when they can make quantum oracle queries. We further define history-free reductions and show that there is a general lifting result allowing to argue security in the quantum random oracle model when there is a reduction in the classical setting. As an example for this technique we will show how to prove the security of signatures following the Full Domain Hash paradigm.