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
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.
Laura Pierson 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
Crypto Reading Group - Seunghoon Lee & Bruno Sterner-Introduction to Coding Theory (Part 1)
Abstract: For this term's reading group, we will be hosting a study group on code-based cryptography with a focus on understanding HQC — the most recent NIST standard for post-quantum KEM/PKE. We will spend 7 weeks going over the necessary material to cover this topic before concluding with state-of-the-art HQC. A week-by-week plan is outlined at the following link: https://www.leonardocolo.com/seminars/Spring26.html.
For the first week, we will cover the basic definitions and properties of coding theory as well as go over Reed-Solomon codes.
|
CombOpt ReadingGroup - Kelly Dance-Contract Design Beyond Hidden-Actions
Abstract: In the classical principal-agent hidden-action contract model, a principal delegates the execution of a costly task to an agent. In order to complete the task, the agent chooses an action from a set of actions, where each potential action is associated with a cost and a success probability to accomplish the task. To incentivize the agent to exert effort, the principal can commit to a contract, which is the amount of payment based on the task's success but not on the hidden-action chosen by the agent.
In this work, we study the contract design framework under binary outcomes where we relax the hidden-action assumption. We introduce new models where the principal is allowed to inspect subsets of actions at some cost that depends on the inspected subset. If the principal discovers that the agent did not select the agreed-upon action through the inspection, the principal can withhold payment. This relaxation of the model introduces a broader strategy space for the principal, who now faces a tradeoff between positive incentives (increasing payment) and negative incentives (increasing inspection).
We devise algorithms for finding the best deterministic and randomized incentive-compatible inspection schemes for various assumptions on the inspection cost function. In particular, we show the tractability of the case of submodular inspection cost functions.
We complement our results by showing that it is impossible to efficiently find the optimal randomized inspection scheme for the more general case of XOS inspection cost functions, and that there is no PTAS for the case of subadditive inspection cost functions."
|
Tutte Colloquium -Jim Geelen-Tangles in graphs and matroids
| Speaker: | Jim Geelen |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: A common strategy in many proofs and algorithms is to begin by decomposing a graph into more highly connected pieces. Decomposition is easy when the goal is to obtain connected or 2-connected pieces, and decomposition into 3- or 4-connected pieces is also straightforward in many settings. For higher levels of connectivity, however, no effective and widely applicable notion of decomposition is currently known. To address this, Robertson and Seymour introduced tangles, which capture the k-connected regions of a graph without decomposing.