Probabilistic Solutions of Equations in the Braid Group
<|reference_start|>Probabilistic Solutions of Equations in the Braid Group: Given a system of equations in a "random" finitely generated subgroup of the braid group, we show how to find a small ordered list of elements in the subgroup, which contains a solution to the equations with a significant probability. Moreover, with a significant probability, the solution will be the first in the list. This gives a probabilistic solution to: The conjugacy problem, the group membership problem, the shortest representation of an element, and other combinatorial group-theoretic problems in random subgroups of the braid group.   We use a memory-based extension of the standard length-based approach, which in principle can be applied to any group admitting an efficient, reasonably behaving length function.<|reference_end|>
@article{garber2004probabilistic,
    title={Probabilistic Solutions of Equations in the Braid Group},
    author={D. Garber, S. Kaplan, M. Teicher, B. Tsaban and U. Vishne},
    journal={Advances in Applied Mathematics 35 (2005), 323--334},
    year={2004},
    doi={10.1016/j.aam.2005.03.002},
    archivePrefix={arXiv},
    eprint={math/0404076},
    primaryClass={math.GR cs.CR math.GT}
}