CS Paper Radar

Daily listing

2026-11-17 · math.GR

1 papers first submitted this day (UTC) in math.GR — math.GR. arXiv announces a day's submissions the next evening, so the newest day fills up over ~24 h.

Score = weighted mean ofCitations 20%Upvotes 10%Code stars 10%Venue 15%Code/data 10%Novelty 15%Momentum 15%Substance 5%how it works

Theory & Algorithms 1

A faster algorithm for commutator length in free groups

cs.DS math.GR ·2026-11-17 ·Zixing Wang
Abstract

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.

0.40