We hope you are enjoying your time in our graduate programs. Check out our course offerings, information about degree completion, the PhD qualifying exams, the PhD lecturing requirement, and instructions on submitting your PhD annual activity report. If you still have some years ahead in your grad studies, you might be interested in applying for scholarships.
If you have any administrative questions, please contact us at cograd@uwaterloo.ca.
Seminars in Combinatorics and Optimization
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. |
Tutte Colloquium -Douglas Stebila-Adding functionality to post-quantum cryptography with variants of the Fujisaki-Okamoto transform
| Speaker: | Douglas Stebila |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: The Fujisaki-Okamoto (FO) transform is a fundamental building block in new post-quantum cryptography standards like NIST's ML-KEM, where it is used to convert a weakly secure public key encryption scheme into a key encapsulation mechanism (KEM) secure against active attackers. In this talk, we'll explore two approaches to add extra security and functionality to post-quantum KEMs by enhancing the FO transform. First, we see how a birthday-style collision argument lets an attacker who collects many ciphertexts halve the security of the FrodoKEM and HQC standards, and how extending the FO transform with public salts thwarts this multi-target attack. Second, we turn to implementation flaws: for 19 months, HQC's reference implementation effectively skipped a security-critical verification step, yet basic correctness tests still passed. We show how the principle of "verifiable verification", via an extension of the FO transform, ties security to functionality, so that an implementation which that skips it visibly breaks.