Events

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)