A fast algorithm to the conjugacy problem on generic braids
| dc.creator | Ko, Ki Hyoung | |
| dc.creator | Lee, Jang Won | |
| dc.date | 2006-11-15 | |
| dc.date | 2006-12-05 | |
| dc.date.accessioned | 2026-07-07T07:32:56Z | |
| dc.date.available | 2026-07-07T07:32:56Z | |
| dc.description | Random braids that are formed by multiplying randomly chosen permutation braids are studied by analyzing their behavior under Garside's weighted decomposition and cycling. Using this analysis, we propose a polynomial-time algorithm to the conjugacy problem that is successful for random braids in overwhelming probability. As either the braid index or the number of permutation-braid factors increases, the success probability converges to 1 and so, contrary to the common belief, the distribution of hard instances for the conjugacy problem is getting sparser. We also prove a conjecture by Birman and González-Meneses that any pseudo-Anosov braid can be made to have a special weighted decomposition after taking power and cycling. Moreover we give polynomial upper bounds for the power and the number of iterated cyclings required. | |
| dc.description | 12 pages, 1 figure. to appear in the Proceedings of the International Workshop on Knot Theory for Scientific Objects: OCAMI Studies Vol 1. Knot Theory for Scientific Objects | |
| dc.identifier | https://arxiv.org/abs/math/0611454 | |
| dc.identifier | http://arxiv.org/abs/math/0611454 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/119286 | |
| dc.subject | Geometric Topology | |
| dc.subject | Group Theory | |
| dc.subject | 20F36; 20F10 | |
| dc.title | A fast algorithm to the conjugacy problem on generic braids | |
| dc.type | text |