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.
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.
Two 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.
Events
Algebraic and Enumerative combinatorics seminar - Kevin Purbhoo- The hook length formula massacree
| Speaker: | Kevin Purbhoo |
| Affiliation: | University of Waterloo |
| Location: | MC 6460 |
Abstract: Around 1900 Young and Frobenius (independently, and through very different techniques) obtained a formula for the dimensions of the irreducible representations of the symmetric group. Some 53 years later, Frame, Robinson and Thrall noticed that the Young-Frobenius formula simplified into the now famous hook length formula. Nowadays there are many proofs, but the hook length formula remains something of a mystery, as if some deeper understanding lies just out of reach. One aspect of this mystery is that none of the proofs seem to indicate how one might come up with the formula in the first place, other than just guessing.
I will attempt to answer that question. It is an improbable tale that meanders through scenes of Young symmetrizers, Schur-Weyl duality, Weyl algebras, elementary combinatorics, and Plücker relations. All because Google's AI gave me a very obviously wrong answer when I was trying to find out the square of a Young symmetrizer.
There will be a pre-seminar presenting relevant background at beginning graduate level starting at 1:30pm in MC 5417.
Crypto Reading Group - Camryn Steckel-Decoding for Quasi-Cyclic Codes
Abstract: This session focuses on decoding questions specific to quasi-cyclic codes. We will discuss syndrome decoding in the quasi-cyclic setting and compare generic ISD methods with approaches that exploit additional structure. The goal is to better understand the tension between efficiency and security, and to prepare the ground for the study of the HQC scheme.
References: [§6.3, 4], [§3, 6], and [§5, 10]
[4] HQC Team. Hamming Quasi-Cyclic (HQC), NIST Submission, 2025.
[6] C. Löndahl, T. Johansson, M. Koochak Shooshtari, M. Ahmadian-Attari, and M. Reza Aref. Squaring attacks on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension. Designs, Codes and Cryptography , vol. 80, pp. 359–377, 2016.
[10] N. Sendrier. Decoding One Out of Many. Post-Quantum Cryptography. PQCrypto 2011. Lecture Notes in Computer Science, vol. 7071, Springer, 2011.
A week-by-week plan is outlined at the following link: https://www.leonardocolo.com/seminars/Spring26.html.
|
CombOpt ReadingGroup - Sina Kalantarzadeh-Designing a PTAS for Philosopher Inequalities under Constant-Depth Laminar Constraints
Abstract: In stochastic online optimization, prophet inequalities under matroid constraints have been studied extensively. The philosopher benchmark(optimal online strategy) is weaker than the prophet benchmark, but it is still not fully understood how well one can compete against the optimal online strategy using polynomial computational power. Pashkovich and Dehaan showed that it is impossible to design a PTAS for computing optimal online strategy in graphic matroids.
In this talk we consider a special class of matroid constraints so called laminar matroids. There are (n) items arriving in a known order, and each item has a probability distribution over its realized value. We are also given a collection of bins on these items, where each bin (B) has a capacity (c(B)). The bins form a laminar family. When an item arrives, its value is revealed, and the algorithm must immediately decide whether to accept or reject it, while respecting all laminar capacity constraints. The goal is to maximize the expected gain of the total value of the accepted items and compare it to the gain of the optimal online policy, rather than to the prophet.
Anari et al. designed a polynomial-time approximation scheme(PTAS) for constant-depth instances, meaning that each item belongs to only a constant number of bins. Their approach uses the fact that the optimal online policy can be formulated as a linear program(LP). We will first examine this LP in the simple case where the laminar family consists of a single bin of capacity one. In general, however, the LP has exponential size and therefore cannot be solved directly in polynomial time. The main idea is to select certain small bins inside the laminar family for which the corresponding subproblems are no longer exponentially large. On these selected parts, one can use the optimal online policy, and then combine these local policies to obtain a global approximation. It remains open whether one can design a PTAS for general laminar families. |