Current students

Subscribe to Current students

Speaker:	Noah Weninger
Affiliation:	University of Waterloo
Location:	MC 5029

Abstract:

In the shortest-path network interdiction problem, the objective is to select a set $X$ of arcs in a directed graph $G=(V,A)$, subject to a knapsack constraint on $X$, such that the shortest $s$-$t$ path length in $(V,A\setminus X)$ is maximized. We present an improved version of the classic Israeli-Wood Benders covering decomposition (2002). Our method is based on new upper and lower bounds for the problem which integrate cleanly into the Benders decomposition, causing many iterations to be skipped. Using similar techniques, we also derive new covering heuristics, which further reduce the running time. In computational experiments, our improved algorithm achieves speedups of up to two orders of magnitude. The speedup is most notable on the more difficult large, dense graphs: we can often solve instances on complete graphs with 1000 vertices and uniformly distributed weights and costs within a few minutes.

This is joint work with Amir Dadpour and Ricardo Fukasawa.

Speaker:	Francisco J. Aragón Artacho
Affiliation:	University of Alicante
Location:	MC 5501

Abstract: When an optimization problem is structured, it is normally advantageous to use this feature when designing algorithms to solve it. Following the divide-and-conquer paradigm, splitting algorithms iteratively solve simpler problems that are defined by separately using some parts of the original problem. In this talk, we will recall some classical methods and present some recent advances in this subject, paying special attention to splitting methods devised by graphs.

Speaker:	Alexandre Zotine
Affiliation:	University of Saarland
Location:	MC 5479

Abstract: An orbital scheme D of type M² = 0 is the closure of a conjugacy class of some set of n × n upper triangular matrices which are nilpotent of order 2. The geometric components of the orbit scheme are called orbital varieties of type M² = 0, and recently their invariants have been connected to statistical mechanics. In the setting of M² = 0, there are combinatorial methods for studying these invariants via the action of the Borel group of upper triangular invertible matrices. In this talk, we introduce a new pipe dream framework for computing and understanding these invariants. This is joint work with Megumi Harada, Illya Kierkosz, Allen Knutson, Emma Naguit, Brett Nasserden, Naveena Rangunathan, and Adam van Tuyl.

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

Speaker:	Audrey Béliveau
Affiliation:	University of Waterloo
Location:	MC 5501

Abstract:

Network meta-analysis (NMA) enables the comparison of multiple medical interventions by combining evidence on their efficacy or safety across clinical trials. Although these models produce rich probabilistic information about how treatments rank, what practitioners often want are simple, interpretable summaries; for example, whether a treatment is likely among the best, or whether one option is likely to outperform another.

The challenge is that, with n treatments, the number of possible questions one can ask about permutations, combinations, or partial orderings of various subsets of treatments grows exponentially. This leads to a large but highly structured combinatorial space, making exhaustive evaluation infeasible.

We develop algorithmic methods to explore this space efficiently and to identify all binary treatment hierarchy statements whose posterior probability exceeds a specified threshold (e.g., 95%). Our approach exploits structure in the ranking space to avoid redundant computations and then prunes conclusions that are logically implied by others, yielding a concise and non-redundant set of results. We illustrate the approach on an NMA of diabetes treatments.

Friday, July 10, 2026 10:30 am - 11:30 am EDT (GMT -04:00)

Crypto Reading Group - Maggie Simmons-HQC Implementation and Optimization

Speaker:	Maggie Simmons
Affiliation:	University of Waterloo
Location:	MC 6029

Abstract:

This week will cover the implementation and optimization of key sub-routines within HQC. We will begin by examining the implementation of Reed-Solomon decoding within HQC, which includes the BCH-view of syndromes, weighted Newton's identity, the Berlekamp-Massey algorithm, and more. We will also discuss high-performance polynomial multiplication via the Karatsuba algorithm and hardware optimization.

References: [3] and [4]

[3] J. Dong, Y. Hou, S. Wang, L. Sha, F. Xiao, Z. Dong, and J. Lin. HIGH: Harnessing GPU Parallelism for Optimized HQC Performance. In IACR Cryptology ePrint Archive, 2026.

[4] HQC Team. Hamming Quasi-Cyclic (HQC), NIST Submission, 2025.

A week-by-week plan is outlined at the following link: https://www.leonardocolo.com/seminars/Spring26.html.

Speaker:	Oliver Pechenik
Affiliation:	University of Waterloo
Location:	MC 6460

Abstract: Standard tableaux are certain grids of numbers that lead a double life in algebraic combinatorics, with distinct roles in geometry and in representation theory. Extending the geometry to K-theory led to a corresponding extension of the combinatorics to a theory of increasing tableaux. I will discuss a longstanding plot by such tableaux to prevent me from explicating their combinatorial dynamics. Despite their reticence, we seem to be uncovering that these tableaux also have a mysterious second life in representation theory.

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

Speaker:	Nathan Benedetto Proenca
Affiliation:	University of Waterloo
Location:	MC 6029

Abstract: Randomization is a powerful technique within theoretical computer science. There is strong theoretical picture studying distinct complexity models with access to random bits, in particular focused on what types of algorithms can be de-randomized. This discussion will not venture into this part of the literature, rather questioning an implicit assumption present when discussing the need for random bits. Why is randomness helpful at all, in particular in the design of rounding algorithms in the SDP literature? Granted, the value of randomness in other contexts is quite explicit. For example, a quicksort implementation uses randomization to avoid worst case inputs. The probabilistic method allows for simple constructions of complex objects by harvesting complexity from a randomness source. But what purpose does randomness serve when rounding a SDP solution into a solution to a NP-hard problem? Why Goemans and Williamson had to use a random hyperplane to turn vectors in the hypersphere into a edge-cut in a graph? This talk attempts to answer this question by presenting a couple of theorems which connect the existence of randomized rounding algorithms to cornerstone results in functional analysis.

Friday, July 3, 2026 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte Colloquium -Oliver Pechenik-Dynamics of Increasing Tableaux

Speaker:	Oliver Pechenik
Affiliation:	University of Waterloo
Location:	MC 5501

Abstract: Standard tableaux are certain grids of numbers that lead a double life in algebraic combinatorics, with distinct roles in geometry and in representation theory. Extending the geometry to K-theory led to a corresponding extension of the combinatorics to a theory of increasing tableaux. I will discuss a long and ongoing program to explicate the combinatorial dynamics of these tableaux, which seems to be revealing that they also have a mysterious second life in representation theory. Despite the algebraic connections, the core problem is fundamentally combinatorial: to give a sufficiently good bijection between tableaux and a set of planar diagrams.

Speaker:	Rian Neogi
Affiliation:	University of Waterloo
Location:	MC 6029

Abstract:

In budget-feasible mechanism design, there is a set of items U. A buyer wishes to purchase a set of items from the sellers of maximum value, where the value of a subset S of items is provided by a valuation function v. Each element e is held by a distinct seller, who incurs a private cost c_e for supplying her item. The buyer also has a budget of B on the total payments made to the sellers. The private costs c_e are known only to the sellers, and not to the buyer. Each seller e reports a cost r_e to the mechanism, which may or may not be equal to her true cost c_e. As a result, a seller may choose to misreport her cost if she sees that she is better off when doing so (for example, the mechanism might be giving her a higher payment under the misreported cost).

Budget-feasible mechanisms have been well-studied over the past 15 years. In this talk, we will introduce a generalization of the setting, where each agent can now hold multiple items. This generalizes the problem into what is known as a multi-parameter domain, which brings about several complications, including strong impossibility results with respect to the typical benchmark of the algorithmic optimum. In lieu of these impossibility results, we propose a novel benchmark for the setting. We prove positive results with respect to this new benchmark, qualitatively matching prior results in single-parameter budget-feasible mechanism design.

This is joint work with Kanstantsin Pashkovich and Chaitanya Swamy, and is to appear in EC 2026.

Speaker:	Jerónimo Valencia-Porras
Affiliation:	University of Waterloo
Location:	MC 6460

Abstract: The totally asymmetric simple exclusion process (TASEP) is a finite Markov chain of particles hopping between adjacent sites on a one-dimensional lattice. The multispecies TASEP is a generalization in which particles have different types. These processes have interesting connections to algebraic combinatorics: the stationary distribution of the TASEP on a circle is connected to Macdonald polynomials at t=0, whereas the stationary distribution of the open-boundary TASEP is connected to Koorwinder polynomials at t=0.

Multiline queues were introduced by Ferrari and Martin (2007) to compute the stationary distribution of the multispecies TASEP on a circle. It has been a long-standing open problem to find a combinatorial formula for the stationary distribution of the multispecies TASEP with open boundaries. Recently, we studied the combinatorics of Ferrari–Martin multiline queues using type A crystals. In this talk, we use crystals of type C to construct an analog of multiline queues and give a combinatorial formula for the stationary distribution of the multispecies open-boundary TASEP for a certain specialization of the boundary parameters. This is joint work with Olya Mandelshtam.

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

Current students

CombOpt ReadingGroup - Noah Weninger-Improved algorithms for shortest-path network interdiction

Tutte Colloquium -Francisco J. Aragón Artacho-Graph-based splitting algorithms for optimization and feasibility problems

Algebraic and Enumerative combinatorics seminar -Alexandre Zotine-A pipe dream framework for orbital varieties of type M² = 0

Tutte Colloquium -Audrey Béliveau-Combinatorial Structure and Algorithms for Treatment Rankings

Crypto Reading Group - Maggie Simmons-HQC Implementation and Optimization

Algebraic and Enumerative combinatorics seminar -Oliver Pechenik-Revenge of the increasing tableau dynamics

CombOpt ReadingGroup - Nathan Benedetto Proenca-Why are SDP Rounding Algorithms Randomized?

Tutte Colloquium -Oliver Pechenik-Dynamics of Increasing Tableaux

CombOpt ReadingGroup - Rian Neogi-Multidimensional Budget-feasible mechanism design

Algebraic and Enumerative combinatorics seminar -Jerónimo Valencia-Porras-Type C multiline queues and the open-boundary TASEP

Contact Info