2014/03/18 by Arkadius Kalka, Kalka, Arkadius, Boaz Tsaban +3
Mathematics · #20C40 #20F36 #20F65 #Algebraic Geometry and Number Theory #Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #Homotopy and Cohomology in Algebraic Topology
paper · pdf · doi:10.48550/arxiv.1403.4622
openalex publication_date 2014/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We solve the simultaneous conjugacy problem in Artin's braid groups and, more generally, in Garside groups, by means of a complete, effectively computable, finite invariant. This invariant generalizes the one-dimensional notion of super summit set to arbitrary dimensions. One key ingredient in our solution is the introduction of a provable high-dimensional version of the Birman--Ko--Lee cycling theorem. The complexity of this solution is a small degree polynomial in the cardinalities of our generalized super summit sets and the input parameters. Computer experiments suggest that the cardinality of this invariant, for a list of order N independent elements of Artin's braid group BN, is generically close to~1.