Abstracts
for the Seminar

Spring 2018

**Speaker: **Alex Yong, University of Illinois Urbana-Champaign

**Title: **Reduced word enumeration, complexity and randomization

**Time:** 2:30 PM, Monday, April 30, 2018

**Place:** Malott 206

**Abstract:** A reduced word of a permutation w is a minimal length expression of w as a product of simple transpositions. The concept is ubiquitous within algebraic combinatorics. I will summarize what is known about enumeration of this set. In joint work (in progress) with Cara Monical and Benjamin Pankow, we prove that a well-known algorithm ("transition") for this problem has, on average, exponential time complexity. Given this context, we devise two simple, but competitive, randomized approximation algorithms. One of these extends to Hecke word enumeration, where significantly fewer results are available.

Back to main seminar page.