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
Graphs and Matroids - Taite LaGrange-Classes of graphs with sub-linear twin-width
| Speaker: | Taite LaGrange |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:Twin-width is a graph and matrix parameter introduced in 2021 by Bonnet, Kim, Thomassé, and Watrigant as essentially a measure of the 'error' between vertex neighbourhoods over a series of vertex contractions. This talk covers some graph classes with unbounded twin-width. We present a tool for obtaining twin-width bounds in general by contracting a graph based on a partition by distinct neighbourhoods. For a graph G on n vertices, we show that if such a partition exists, then the twin-width of G is at worst sub-linear with respect to n. We use this to obtain an upper bound on the twin-width of interval graphs and of graphs with bounded VC dimension. The latter implies that hereditary classes have sub-linear twin-width if and only if they have bounded VC dimension.
Algebraic & Enumerative Combinatorics - Stephan Pfannerer-Rotation-invariant web bases from hourglass plabic graphs
| Speaker: | Stephan Pfannerer |
| Affiliation: | University of Waterloo |
| Location: | MC 5417 |
Abstract:
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm in MC 5417.
Crypto Reading Group - Huanhuan Chen-Updatable Encryption
Abstract:Updatable encryption (UE) enables a cloud server to update ciphertexts using client-generated tokens. There are two types of UE: ciphertext-independent (c-i) and ciphertext-dependent (c-d). In terms of construction and efficiency, c-i UE utilizes a single token to update all ciphertexts. The update mechanism relies mainly on the homomorphic properties of exponentiation, which limits the efficiency of encryption and updating. Although c-d UE may seem inconvenient as it requires downloading parts of the ciphertexts during token generation, it allows for easy implementation of the Dec-then-Enc structure. This methodology significantly simplifies the construction of the update mechanism. Notably, the c-d UE scheme proposed by Boneh et al. (ASIACRYPT’20) has been reported to be 200 times faster than prior UE schemes based on DDH hardness, which is the case for most existing c-i UE schemes. Furthermore, c-d UE ensures a high level of security as the token does not reveal any information about the key, which is difficult for c-i UE to achieve. However, previous security studies on c-d UE only addressed selective security; the studies for adaptive security remain an open problem. In this study, we make three significant contributions to ciphertext-dependent updatable encryption (c-d UE). Firstly, we provide stronger security notions compared to previous work, which capture adaptive security and also consider the adversary’s decryption capabilities under the adaptive corruption setting. Secondly, we propose a new c-d UE scheme that achieves the proposed security notions. The token generation technique significantly differs from the previous Dec-then-Enc structure, while still preventing key leakages. At last, we introduce a packing technique that enables the simultaneous encryption and updating of multiple messages within a single ciphertext. This technique helps alleviate the cost of c-d UE by reducing the need to download partial ciphertexts during token generation.
|