Events

Abstract: It is well known that the maximum cut size of a graph is at least half its number of edges. But how small can this difference be? Using random hyperplane rounding, a technique from semidefinite optimization, Balla, Janzer, and Sudakov obtained a lower bound on this difference in terms of the vector chromatic number, recovering known extremal bounds for $C_r$-free graphs. I will present their argument and show that the constant in their vector-chromatic bound is optimal by constructing a random sphere graph.

Abstract: Quantum Key Distribution (QKD) uses the laws of Quantum Mechanics to allow two parties to produce a shared secret key only known to them without it's security relying on the computational hardness. In this presentation, we will introduce the QKD protocol BB84, and present how it is secure against various attacks. We will also discuss two major phases in BB84: the information reconciliation phase between keys of sender and receiver via error correcting codes and the privacy amplification phase where two communicating parties distill highly secret shared key from a larger body of a shared key, which is only partially secret. Finally, we will give a brief overview of Muckle-based hybrid authenticated key exchange (AKE) protocols.

Abstract: The Mantaci–Reutenauer algebra is a subalgebra of the group algebra of signed permutations which has close ties to symmetric functions, descents, and characters. In this talk, we explore its representation theory and explain how it is governed by simple operations on signed versions of classical combinatorial objects (i.e. partitions, necklaces). This builds on a well-studied type A story for Solomon's "descent algebra". The representation-theoretic data we will consider include the Cartan matrix, the representation type, and a conjectural Ext-quiver; we will explain these notions during the talk. This is ongoing joint work with Alice Dell'Arciprete.

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

Abstract: We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering a longstanding open question in graph streaming literature since the introduction of the model. Our proof consists of two main parts:

 1. Blueprint framework: reducing the problem of proving lower bounds for semi-streaming matching to constructing certain combinatorial objects which we call blueprints; and,

 2. Blueprint construction: an optimal construction of such blueprints usable within this framework.

 Putting these two parts together implies our semi-streaming matching lower bound.

Based on joint work with Max Jiang and Mars Xiang in https://arxiv.org/abs/2607.14644 (STOC 2026) and https://arxiv.org/abs/2607.14656 (arXiv; July 2026)