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
Combinatorics and Optimization reading group | Arkaprava Choudhury, Proof of the Sunflower Conjecture
| Speaker: | Arkaprava Choudhury |
| Affiliation: | University of Waterloo |
| Room: | MC 6029 |
Abstract: A $k$-sunflower is a family of $k$ distinct sets whose pairwise intersections all coincide. The Erd\H{o}s--Szemer\'edi conjecture asserts that for every $k \ge 3$ there is a constant $c_k < 2$ such that any $k$-sunflower-free family $\mathcal{F} \subseteq 2^{[n]}$ satisfies $|\mathcal{F}| \le c_k^{\,n}$. Bucic, He, and Lee recently proved this with an explicit bound.
In this talk we survey the problem and its place among sunflower questions, then work through the proof, centered on a vector-sunflower argument. We also discuss how the result relates to a related problem, the uniform Erd\H{o}s--Rado conjecture, which it does not settle. No prior background is assumed.
Graphs and Matroids | Hidde Koerts, Faster 3-colouring algorithm for graphs of diameter 3
| Speaker: | Hidde Koerts |
| Affiliation: | University of Waterloo |
| Room: | MC 6029 |
Abstract: Determining whether a graph is k-colourable is a famously hard computational problem. Even when placing significant restrictions on the graph, the resulting problem is often NP-hard. In this talk, we focus on the case of restricting the diameter. Under the Exponential Time Hypothesis, there does not exist a sub-exponential algorithm for 3-colouring diameter-4 graphs or for 4-colouring diameter-2 graphs. Hence, the interesting remaining cases are 3-colouring graphs of diameter 2 or 3. We show that 3-colouring diameter-3 graphs can be solved in 2^O(n^{2/3−ε}) for any ε < 1/33 by providing an algorithm based on a structural result. This improves on the previous best known algorithm due to Dębski, Piecyk and Rzążewski.
This talk is based on joint work with Carla Groenland and Sophie Spirkl.
Crypto Reading Group on quantum computing | Douglas Stebila, QKD Security
| Speaker: | Douglas Stebila |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract: Having seen the BB84 quantum key distribution protocol last week, this week we’ll see what it means for QKD to be secure, following the basic principle that “information gain implies disturbance”. We’ll talk about what authentication is needed for QKD’s security guarantees to hold, and other factors like device security and finite key effects.