Timeline for Is conjugacy problem hard in braid group?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 16, 2020 at 1:38 | comment | added | dvitek | @RyanBudney Is it accurate to call Calvez's algorithm quadratic? Is anything known about the effectiveness of the constant in the Masur-Minsky linear-conjugator bound? Otherwise it seems like the algorithm is quadratic in word-length for a fixed number of strands, but could blow up very quickly as the number of strands increases. | |
| Mar 14, 2017 at 11:14 | comment | added | Derek Holt | I was under the impression that, due to progress in theoretical results, the conjugacy problem in braid groups was abandoned several years ago as a serious candidate for cryptographic protocols. | |
| Mar 14, 2017 at 7:01 | comment | added | Meysam Ghahramani | @RyanBudney, That paper is very interesting for me. Is this means that cryptographic schemes which are based on conjugacy problem in braid groups are not reliable? | |
| Mar 14, 2017 at 4:19 | comment | added | Ryan Budney | It would appear quite likely that the conjugacy problem can be solved rather quickly -- perhaps polynomial time. For example, the paper arxiv.org/pdf/1112.0165.pdf describes a quadratic-time algorithm to determine if a braid is pseudo-anosov, periodic or reducible. That gets you much of the way to the result. | |
| Mar 14, 2017 at 4:05 | history | asked | Meysam Ghahramani | CC BY-SA 3.0 |