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
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.
Sepehr Hajebi wins Graduate Research Excellence Award, Mathematics Doctoral Prize, and finalist designation for Governor General's Gold Medal
The Mathematics Doctoral Prizes are given annually to recognize the achievement of graduating doctoral students in the Faculty of Mathematics. The Graduate Research Excellence Awards are given to students who authored or co-authored an outstanding research paper.
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.
Events
Crypto Reading Group - Elnaz Hessami Pilehrood-Shadowfax: Hybrid Security and Deniability for AKEMs
Abstract:As cryptographic protocols transition to post-quantum security, most adopt hybrid solutions combining classical and post-quantum assumptions. This shift often sacrifices efficiency, compactness, or even security. One such property is deniability, which enables users to plausibly deny authorship of potentially incriminating messages. While classical protocols like X3DH key agreement (used in Signal and WhatsApp) provide deniability, post-quantum protocols like PQXDH and Apple’s iMessage with PQ3 do not. This work addresses this gap by investigating how to efficiently preserve deniability in post-quantum protocols. Specifically, we propose two hybrid schemes for authenticated key encapsulation mechanisms (AKEMs). The first is a black-box construction that preserves deniability when both constituent AKEMs are deniable. The second is Shadowfax, a non-black-box AKEM that achieves hybrid security, integrating a classical non-interactive key exchange, a post-quantum key encapsulation mechanism, and a post-quantum ring signature. Shadowfax satisfies deniability in both dishonest and honest receiver settings, relying on statistical security in the former and on a single pre- or post-quantum assumption in the latter. Finally, we provide several portable implementations of Shadowfax. When instantiated with standardised components (ML–KEM and Falcon), Shadowfax yields ciphertexts of 1 728 bytes and public keys of 2 036 bytes, with encapsulation and decapsulation costs of 1.8M and 0.7M cycles on an Apple M1 Pro. |
Tutte Colloquium -Tammy Kolda -Fast and Accurate Tensor Decompositions on Infinite-Dimensional Function Spaces
| Speaker: | Tammy Kolda |
| Affiliation: | MathSci.ai |
| Location: | MC 5501 |
Abstract: Tensor decompositions are fundamental tools in scientific computing and data analysis. In many applications — such as simulation data on irregular grids, surrogate modeling for parameterized PDEs, or spectroscopic measurements — the data has both discrete and continuous structure, and may only be observed at scattered sample points. The CP-HIFI (hybrid infinite-finite) decomposition generalizes the Canonical Polyadic (CP) tensor decomposition to settings where some factors are finite-dimensional vectors and others are functions drawn from infinite-dimensional spaces — a natural framework when the underlying data has continuous structure. The decomposition can be applied to a fully observed tensor (aligned) or, when only scattered observations are available, to a sparsely sampled tensor (unaligned). Current methods compute CP-HIFI factors by solving a sequence of dense linear systems arising from regularized least-squares problems, but these direct solves become computationally prohibitive as problem size grows. We propose new algorithms that achieve the same accuracy while being orders of magnitude faster. For aligned tensors, we exploit the Kronecker structure of the system to efficiently compute its eigendecomposition without ever forming the full system, reducing the solve to independent scalar equations. For unaligned tensors, we introduce a preconditioned conjugate gradient method applied to a reformulated system with favorable spectral properties. We analyze the computational complexity and memory requirements of the new methods and demonstrate their effectiveness on problems with smooth functional modes. I will also discuss the “First Proof” project, which aims to understand the capabilities of AI systems on problems that come up in math research, and the role that results from that experiment played in this project.
Algebraic and Enumerative combinatorics seminar - Tyler Dunaisky-Cosmological Correlators and Triangulating the Dual Cosmological Polytope
| Speaker: |
Tyler Dunaisky
|
| Affiliation: | Purdue University |
| Location: | MC 5417 |
Abstract: A cosmological correlator is an Euler integral, associated to a graph G, which encodes information about the state of the early universe. Evaluation of these integrals is extremely challenging, even in simple cases. However, it turns out the integrand can be identified with the so-called canonical form of the cosmological polytope, revealing a rich combinatorial structure and allowing the application of techniques from commutative algebra. I'll sketch my contribution to this story and advertise the fledgling field of positive geometry, which seeks to generalize the notion of canonical forms to geometric objects more exotic than polytopes.
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm.