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
Algebraic & Enumerative Combinatorics - Maria Gillespie-A Positive Combinatorial Rule for Psi Class Products on Multicolored Spaces
| Speaker: | Maria Gillespie |
| Affiliation: | Colorado State University |
| Location: | MC 5417 |
Abstract: We use a new combinatorial construction and a sign-reversing involution to simplify an alternating sum that arises naturally in intersection theory on moduli spaces of curves. In particular, it is well known that a product of ψ classes on the moduli space M₀,ₙ-bar, the most commonly studied compactification of the moduli space M₀,ₙ of choices of n distinct marked points on ℙ¹, is equal to a multinomial coefficient and has many natural combinatorial interpretations.
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm in MC 5417.
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.