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 | Mahtab Alghasi, Dyadic Fractional Packings of T-Joins
| Speaker: |
Mahtab Alghasi |
| Affiliation: | University of Waterloo |
| Room: | MC 6029 |
Abstract: Let G be a graph and let T be a nonempty set of vertices of even cardinality. A T-join is an edge set whose odd-degree vertices are precisely T, and a T-cut is a cut with an odd number of terminals on each side. A classical consequence of the Edmonds–Johnson theorem is that the minimum cardinality of a T-cut equals the maximum value of a fractional packing of T-joins. An optimal packing need not be integral or even half-integral, but can its coefficients always be chosen with denominators that are powers of two?
I’ll present the affirmative answer of Ahmad Abdi, Gérard Cornuéjols, and Zuzanna Palion, which establishes Seymour’s Dyadic Conjecture for clutters of T-joins. I’ll outline how the proof combines Lovász’s matching-lattice theorem with dyadic feasibility and combinatorial contraction and gluing arguments.
*We switched to a closely related topic after learning that the author will present the work the following day, Tuesday, November 24, at 6:30 p.m. Eastern. For those interested you can also join the talk online. Sorry for any inconvenience caused by the change. https://researchseminars.org/seminar/SFUOR
Graphs and Matroids | Hadas Barabash, Finding full immersions is fixed-parameter tractable in labeled tour graphs
| Speaker: | Hadas Barabash |
| Affiliation: | Georgia Tech |
| Room: | MC 6029 |
Abstract: We give an $O_{\mathcal{H}}(n^5)$-time algorithm to test whether an $n$-vertex labeled tour graph has a full immersion isomorphic to a labeled tour graph $\mathcal{H}$. A \emph{labeled tour graph} is a connected $4$-regular graph whose edges are labeled by binary vectors of fixed length. To obtain a \emph{full immersion}, a vertex may be removed only by pairing up its four incident edges and ``splitting off'' both pairs, summing the labels within each pair. Even for one-bit labels, no polynomial-time algorithm was previously known for arbitrary fixed $\mathcal{H}$. Our results have implications for \emph{vertex-minors}, whose study is motivated by applications in quantum networking.
Cryptography Seminar | Rolfe Schmidt, Making the Signal Protocol Quantum Safe: Where We Are and What’s Next
| Speaker: | Rolfe Schmidt |
| Affiliation: | Signal |
| Location: | United College, Room 105 |
Abstract: In 2023 Signal deployed PQXDH, a small change to the handshake that protects new conversations against adversaries who record traffic today and decrypt it with a future quantum computer. Two gaps remain: post-compromise security in the ratchet and authentication in the handshake both still rely on elliptic curves. This talk describes how we closed the first and how we plan to close the second.
In the first part, we look at the challenge of building a post-quantum ratcheted messaging protocol in a bandwidth-constrained setting, and build up Signal’s Sparse Post-Quantum Ratchet, deployed in 2025, step by step through a series of simpler protocols.
In the second part, we look ahead to a new handshake that completes the transition of Signal’s 1:1 messaging with hybrid, deniable authentication. While the post-quantum ratchet feels like an engineering variation on the classical one, the post-quantum key agreement takes a very different shape. Our need to save bandwidth still drives plenty of engineering, including Merkle trees, Falcon signature recovery modes, and context-specific optimizations.
I’ll close with open questions and a brief look at what it will take to make the rest of the Signal app quantum safe.