Current students

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.

Abstract: Praeger-Xu graphs are a family of multicovers of cycles, known for some of their surprising properties. A fundamental observation is that these graphs can be constructed from De Bruijn graphs. In this presentation, we will generalize the definition of De Bruijn graphs to create a broader family of multicovers. Finally, we will compute the automorphism group and show some applications of our constructions. This is a joint work with Ci Xuan Wu.

Abstract: We discuss the challenging problem of finding pairs of consecutive smooth integers, which we refer to as a smooth twin. In other words the largest prime factor in the twin is relatively small. This computational number theoretic problem has appeared in the context of isogeny-based cryptography whereby a select number of cryptosystems use such twins as part of their parameter setup. The challenging part to the problem is finding smooth twins whose largest prime factor is as small as possible. Prior to this work, twins of this nature have at most 74-bits which is much too small for cryptographic relevance. We bridge this gap by presenting a new method that finds significantly larger smooth twins with as small as possible smoothness bound. The idea of our algorithm is based on the well known and studied problem of finding short vectors in a well constructed lattice. We report a 196-bit smooth twin which falls in this regime as well as a few larger twins that have small (but not the smallest) smoothness bounds.

Abstract: 

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm in MC 5417.

Abstract: The (parallel) pebbling game is a useful abstraction for analyzing the resources (e.g., space, space-time, amortized space-time) needed to evaluate a function f with a static data-dependency graph G on a (parallel) computer. The underlying question is purely combinatorial: what tradeoffs does a directed acyclic graph (DAG) force between storing intermediate values and recomputing them? This viewpoint has been particularly influential in cryptography, where many “Memory-Hard Function” (MHF) constructions can be modeled by evaluating a fixed DAG.

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.