Reduced word enumeration, complexity, and randomization (Q2144333)

Summary: A reduced word of a permutation \(w\) is a minimal length expression of \(w\) as a product of simple transpositions. We examine the computational complexity, formulas and (randomized) algorithms for their enumeration. In particular, we prove that the Edelman-Greene statistic, defined by \textit{S. Billey} and \textit{B. Pawlowski} [J. Comb. Theory, Ser. A 127, 85--120 (2014; Zbl 1300.05313)], is typically exponentially large. This implies a result of \textit{B. Pawlowski} [Permutation diagrams in symmetric function theory and Schubert calculus. Seattle, WA: University of Washington (PhD Thesis) (2014), \url{https://digital.lib.washington.edu/researchworks/bitstream/handle/1773/26117/Pawlowski_washington_0250E_13742.pdf?sequence=1}], that it has exponentially growing expectation. Our result is established by a formal run-time analysis of Lascoux and Schützenberger's transition algorithm [\textit{A. Lascoux} and \textit{M.-P. Schützenberger}, Lett. Math. Phys. 10, 111--124 (1985; Zbl 0586.20007)]. The more general problem of Hecke word enumeration, and its closely related question of counting set-valued standard Young tableaux, is also investigated. The latter enumeration problem is further motivated by work on Brill-Noether varieties due to \textit{M. Chan} and \textit{N. Pflueger} [Trans. Am. Math. Soc. 374, No. 3, 1513--1533 (2021; Zbl 1464.14032)] and \textit{D. Anderson} et al. [``K-classes of Brill-Noether loci and a determinantal formula'', Int. Math. Res. Not. 2022, No. 16, 12653--12698 (2022; \url{doi:10.1093/imrn/rnab025})]. We also state some related problems about counting computational complexity.