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 and enumerative combinatorics seminar - Ian George-Enumerating Convex Sets in Posets
| Speaker: | Ian George |
| Affiliation: | University of Waterloo |
| Location: | MC 5417 |
Abstract: Causal Set Theory (CST) is a theory of quantum gravity where spacetime is taken to be a locally finite poset, called a causal set. A central problem in CST is to determine physically relevant properties from the purely combinatorial information of the causal set. In 2014 Glaser and Surya demonstrated that the distribution of interval sizes of a causal set sprinkled into a region of Minkowski space contains information about the dimension of the underlying spacetime. In 2026 Surya showed that this distribution can be used to define a “closeness” function on causal sets that distinguishes by dimension and global topology. In this talk we present work motivated by these results which investigates the more general notion of convex sets, instead of intervals, of a poset. First, we will introduce a generating polynomial for convex sets in a finite poset and explore some of its properties. We will then show that this polynomial is a complete invariant for the family of series-parallel posets. Lastly, we discuss early results on the utility of this polynomial in CST. The pre-seminar will introduce relevant background on CST.
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm.
Crypto Reading Group - Mohammad Hajiabadi-Challenges in Realizing CCA in Advanced Encryption Schemes
Abstract:CCA security is a fundamental notion in cryptography. There are standard techniques to generically achieve CCA security for all-or-nothing type public-key encryption schemes, such as heuristic approaches based on Fujisaki–Okamoto, or constructions in the standard model using tools like hinting PRGs. However, in more advanced settings, such as functional encryption or threshold encryption, these generic approaches break down. Moreover, defining CCA security in these settings is itself non-trivial and leads to subtle definitional challenges. In this talk, I will discuss these issues, highlight the key obstacles, and present several open problems, along with possible directions for addressing them.
|
Tutte Colloquium -Therese Biedl-Planar graph drawing, meet MSOL
| Speaker: | Therese Biedl |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: It is well-known that every planar graph has a planar drawing with straight-line segments, even if vertices are restricted to lie on a grid with linear coordinates. In this talk, we will study the question of finding planar graph drawings where the height H of the grid is as small as possible. Dujmovic et al gave an FPT-algorithm that finds the minimum height. However, it is not particularly adaptable to closely related problems, such as finding rectilinear drawings of minimum height. We therefore study a new and completely different approach to test whether a graph has a drawing of height H. Since such graphs have pathwidth O(H), a natural approach is to appeal to Courcelle's theorem. This requires phrasing the problem in so-called monadic second-order logic (MSOL), but MSOL supports neither arbitrarily large integers nor permutations, making it difficult to use for graph drawing problems. In this talk, we show that with some detours we can phrase the question of whether G has a straight-line drawing of height H in a radically different way ("no face has a fish") that can be easily expressed in MSOL.