{"id":"arxiv/2611.22303","url":"https://arxiv.org/abs/2611.22303","tags":["cs.DS","math.GR"],"score":0,"title":"A faster algorithm for commutator length in free groups","domain":"cs.DS","source":"arxiv","authors":["Zixing Wang"],"reviews":0,"subject":"cs.DS","summary":"We compute the commutator length $\\cl(w)$ of a reduced word $w\\in[F,F]$ of length $M$ in a free group. Given a target $g\\ge1$, a deterministic algorithm decides $\\cl(w)\\le g$ and, when it holds, returns a decomposition into at most $g$ commutators, in $O(M^{3g})$ steps; trying $g=1,2,\\dots$ gives $\\cl(w)$ in $O(M^{3\\cl(w)})$ steps. For $g=1$ the same test takes $O(M)$ expected steps on a uniformly random reduced input in $[F,F]$. All bounds are in the unit-cost model.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-17","reactions":{}}