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 - Leonardo Colò-IS-CUBE: An isogeny-based compact KEM using a boxed SIDH diagram
Abstract: Isogeny-basedcryptographyisoneofthecandidatesforpost- quantum cryptography. One of the benefits of using isogeny-based cryptography is its compactness. In particular, a key exchange scheme SIDH allowed us to use a 4λ-bit prime for the security parameter λ. Unfortunately, SIDH was broken in 2022 by some studies. After that, some isogeny-based key exchange and public key encryption schemes have been proposed; however, most of these schemes use primes whose sizes are not guaranteed as linearly related to the security parameter λ. As far as we know, the remaining schemes have not been implemented due to the computation of isogenies of high dimensional abelian varieties, or they need to use a “weak” curve (i.e., a curve whose endomorphism ring is known) as the starting curve. In this study, we propose a novel compact isogeny-based key encapsula- tion mechanism named IS-CUBE via Kani’s theorem and a 3-dimensional SIDH diagram. A prime used in IS-CUBE is of the size of about 8λ bits, and we can use a random supersingular elliptic curve for the starting curve. The public key of IS-CUBE is about 3 times larger than that of SIKE, and the ciphertext of IS-CUBE is about 4 times larger than that of SIKE from theoretical estimation. In practice, compared to FESTA, the public key of IS-CUBE is slightly larger and its ciphertext is slightly smaller.
The core idea of IS-CUBE comes from the hardness of some already known computational problems and a novel computational problem (the Long Isogeny with Torsion (LIT) problem), which is the problem to compute a hidden isogeny from two given supersingular elliptic curves and information of torsion points of relatively small order.
|
Tutte Colloquium -Kathie Cameron-Reconfiguration of Vertex Colourings
| Speaker: | Kathie Cameron |
| Affiliation: | Wilfrid Laurier University |
| Location: | MC 5011 |
Abstract: A k-colouring of a graph is an assignment of at most k colours to its vertices so that the ends of each edge get different colours. We consider two types of “reconfiguration steps” for transforming a given k-colouring into a target k-colouring. The first is to change the colour of a vertex to a colour which does not appear on any of the vertices it is adjacent to. We say that a graph G is recolourable if for every k greater than its chromatic number, any k-colouring of G can be transformed into any other by these reconfiguration steps. The second (more general) type of reconfiguration step is Kempe swaps. We call a graph Kempe connected if for every k, any k-colouring can be transformed into any other by Kempe swaps.
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.