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.