Seminar

Abstract: The order dimension of a partially ordered set (poset), which is often difficult to compute, is a measure of its complexity. Dilworth proved that the dimension of a distributive lattice is the width of its subposet on its join-irreducible elements. We generalize this result by showing that the dimension of a semidistributive extremal lattice is the chromatic number of the complement of its Galois graph (see Section 3.5 of arXiv:2511.18540). We apply this result to prove that the dimension of the lattice of torsion classes of a gentle tree with n vertices is equal to n. No advanced background is required to follow the talk.

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

Title: Jeu de Taquin for Mixed Insertion and a Problem of Soojin Cho

Abstract: 

Serrano (2010) introduced the shifted plactic monoid, governing Haiman's (1989) mixed insertion algorithm, as a type B analogue of the classical plactic monoid that connects jeu de taquin of Young tableaux with the Robinson–Schensted–Knuth insertion algorithm. Serrano proposed a corresponding definition of skew shifted plactic Schur functions. Cho (2013) disproved Serrano's conjecture regarding this definition, by showing that the functions do not live in the desired ring and hence cannot provide an algebraic interpretation of tableau rectification or of the corresponding structure coefficients. Cho asked for a new definition with particular properties. We introduce such a definition and prove that it behaves as desired. We also introduce the first jeu de taquin theory that computes mixed insertion. This is joint work with Oliver Pechenik.

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

Abstract:Twin-width is a notion introduced in 2020 by Bonnet, Kim, Thomassé and Watrigant  which provides a unified perspective on a range of important graph classes, encompassing both sparse and dense classes. Many graph classes ranging from planar graphs, H-minor-free graphs to proper interval graphs and graphs of bounded cliquewidth have bounded twin-width. This new perspective also allows us to establish powerful properties such as tractability of First-Order model checking on many graph classes and (polynomial) χ-boundedness in a unified way. Twin-width is now considered an important part of the toolbox for structural graph theory, algorithms design, logic on finite graphs and data structure.

Abstract: For all positive integers l and r, we determine the maximum number of elements of a simple rank-r positroid without the rank-2 uniform matroid U(2, l+2) as a minor, and characterize the matroids with the maximum number of elements. This result continues a long line of research into upper bounds on the number of elements of matroids from various classes that forbid U(2, l+2) as a minor, including works of Kung, of Geelen–Nelson, and of Geelen–Nelson–Walsh. This is the first paper to study positroids in this context, and it suggests methods to study similar problems for other classes of matroids, such as gammoids or base-orderable matroids. This project is based on joint work with Zach Walsh.

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

Abstract:  FrodoKEM is a lattice-based Key Encapsulation Mechanism (KEM) based on unstructured lattices. From a security point of view this makes it a conservative option to achieve post-quantum security, hence why it is favored over the NIST winners by several European authorities (e.g., German BSI and French ANSSI). Relying on unstructured instead of structured lattices (e.g., CRYSTALS-Kyber) comes at the cost of additional memory usage, which is particularly critical for embedded security applications such as smart cards. For example, prior FrodoKEM-640 implementations (using AES) on Cortex-M4 require more than 80 kB of stack making it impossible to run on embedded systems. In this work, we explore several stack reduction strategies and the resulting time versus memory trade-offs. Concretely, we reduce the stack consumption of FrodoKEM by a factor 2–3× compared to the smallest known implementations with almost no impact on performance. We also present various time-memory trade-offs going as low as 8 kB for all AES parameter sets, and below 4 kB for FrodoKEM-640. By introducing a minor tweak to the FrodoKEM specifications, we additionally reduce the stack consumption down to 8 kB for all the SHAKE versions. As a result, this work enables FrodoKEM on embedded systems.

Abstract: Suppose that you are given an ordering of the elements of a $k$-connected matroid, and you want to remove the elements one at a time, in the given order, keeping the intermediate matroids as highly connected as possible. How much connectivity can you keep?

Abstract:  In this talk, we demonstrate a connection between log-concavity statements and sampling algorithms via high-dimensional expanders and Lorentzian polynomials. To do this, we first discuss two conjectures which were resolved about 5-10 years ago: one on the log-concavity of independent sets of matroids (due to Brändén-Huh and Anari-Liu-Oveis Gharan-Vinzant), and one on efficiently sampling bases of matroids (due to Anari-Liu-Oveis Gharan-Vinzant). From there we will present some new results on generalized graph colorings which extend these and other previous results. In particular, we will discuss how this can be used to obtain log-concavity statements and sampling algorithms for linear extensions of posets. Joint work with Kasper Lindberg and Shayan Oveis Gharan.

Abstract: The spectrum of a graph is closely related to many graph parameters. In particular, the spectral gap of a regular graph which is the difference between its valency and second eigenvalue, is widely seen an algebraic measure of connectivity and plays a key role in the theory of expander and Ramanujan graphs. In this talk, I will give an overview of recent work studying the maximum order v(k,\theta)  of a regular graph (bipartite graph or hypergraph) of given valency k whose second largest eigenvalue is at most a given value \theta. This problem can be seen as a spectral Moore problem and has connections to Alon-Boppana theorems for graphs and hypergraphs and with the usual Moore or degree-diameter problem. 

Abstract: A (t,n)-threshold signature scheme splits a signing key among "n" participants so that any "t" can jointly produce a valid signature under a single public key, while fewer than "t" cannot. There are three common types of threshold signature schemes: (i) Robust schemes, which guarantee signature production provided at least "t" parties are honest; (ii) Identifiable-abort schemes, which may fail to produce a signature but expose at least one misbehaving signer; and (iii) Simple schemes, which guarantee neither robustness nor identifiable abort, but output a valid signature when "t" honest participants collaborate without deviating from the protocol.

Motivated by NIST's recent emphasis on post-quantum multiparty and threshold designs, this talk presents a new approach to centralized, lattice-based (t,n)-threshold signatures. We first construct a (t,n)-threshold one-time signature and then upgrade it to a many-time scheme by combining it with a long-term signature so that all threshold signatures verify under a single public key.