Current students

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.

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.