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
Graphs and Matroids - Stephen Arndt-Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
| Speaker: | Stephen Arndt |
| Affiliation: | Carnegie Mellon University |
| Room: | MC 5417 |
Abstract:We study algorithmic matroid intersection coloring. We give the first polynomial-time O(1)-approximation algorithm to color O(1) general matroids. Notably, for two general matroids we achieve a 2-approximation. Furthermore, we give a fully polynomial randomized approximation scheme (FPRAS) for coloring the intersection of two matroids when the maximum chromatic number is large. This yields the first polynomial-time algorithm for an asymptotic variant of Rota's Basis Conjecture.
Algebraic and Enumerative combinatorics seminar - Sergio Alejandro Fernandez de Soto Guerrero-New combinatorial possibilities to describe (quotients of) positroids
| Speaker: | Sergio Alejandro Fernandez de Soto Guerrero |
| Affiliation: | TU Graz |
| Location: | MC 5479 |
AbstractPositroids were introduced by Postnikov in 2006 as a special class of matroids with nice combinatorial properties. Since 2008, starting with Suho Ho, several attempts have been made to describe the poset of quotients for this class of matroids in a combinatorial way. However, these descriptions are incomplete and always come from the same perspective. That is why we will explore new combinatorial objects and the context in which they arise (magic, polytopes, and antisymmetric algebras) to see if it is possible to describe this poset.
There will be a pre-seminar presenting relevant background at beginning graduate level starting at 1:30pm in MC 5417.
Crypto Reading Group - Pranshu Kumar & John Premkumar & Karaneh Keypoor-Quasi-Cyclic Codes
Abstract: This session is devoted to quasi-cyclic codes, one of the main structured code families used in modern code-based cryptography. We will introduce their definition and main properties, and explain why their additional algebraic structure is both useful for efficiency and delicate from a security perspective. This week will provide the background needed to understand HQC and related constructions.
|