Geodesic
Randomness and complexity in matrix groups
Fundamentalʹnaâ i prikladnaâ matematika, Tome 22 (2019) no. 4, pp. 253-262.

Voir la notice de l'article provenant de la source Math-Net.Ru

We reflect on how to define the complexity of a matrix and how to sample a random invertible matrix. We also discuss a related issue of complexity of algorithms in matrix groups. 
@article{FPM_2019_22_4_a16,
     author = {V. Shpilrain},
     title = {Randomness and complexity in matrix groups},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {253--262},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2019_22_4_a16/}
}
TY  - JOUR
AU  - V. Shpilrain
TI  - Randomness and complexity in matrix groups
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2019
SP  - 253
EP  - 262
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2019_22_4_a16/
LA  - ru
ID  - FPM_2019_22_4_a16
ER  - 
%0 Journal Article
%A V. Shpilrain
%T Randomness and complexity in matrix groups
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2019
%P 253-262
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2019_22_4_a16/
%G ru
%F FPM_2019_22_4_a16
V. Shpilrain. Randomness and complexity in matrix groups. Fundamentalʹnaâ i prikladnaâ matematika, Tome 22 (2019) no. 4, pp. 253-262. http://geodesic.mathdoc.fr/item/FPM_2019_22_4_a16/

[1] Lindon R., Shupp P., Kombinatornaya teoriya grupp, Mir, M., 1980

[2] Sanov I. N., “Svoistvo odnogo predstavleniya svobodnoi gruppy”, DAN SSSR, 57:7 (1947), 657–659 | MR | Zbl

[3] Akemann G., Baik J., Di Francesco P., The Oxford Handbook of Random Matrix Theory, Oxford Univ. Press, Oxford, 2015 | MR | Zbl

[4] Bassino F., Nicaud C., Weil P., “Generic properties of subgroups of free groups and finite presentations”, Contemp. Math., 677, 2016, 1–44 | MR

[5] Bromberg L., Shpilrain V., Vdovina A., “Navigating in the Cayley graph of $\mathrm{S}\mathbb{L}_2(\mathbb{F}_p)$ and applications to hashing”, Semigroup Forum, 94:2 (2017), 314–324 | MR | Zbl

[6] Chorna A., Geller K., Shpilrain V., “On two-generator subgroups of $\mathrm{S}\mathbb{L}_2(\mathbb{Z})$, $\mathrm{S}\mathbb{L}_2(\mathbb{Q})$ and $\mathrm{S}\mathbb{L}_2(\mathbb{R})$”, J. Algebra, 478 (2017), 367–381 | MR | Zbl

[7] Epstein D. B. A., Cannon J., Holt D. F., Levy S. V. F., Paterson M. S., Thurston W. P., Word Processing in Groups, Jones and Bartlett, Boston, 1992 | MR | Zbl

[8] Kapovich I., Musings on generic-case complexity, arXiv: 1505.03218

[9] Kapovich I., Myasnikov A. G., Schupp P., Shpilrain V., “Average-case complexity and decision problems in group theory”, Adv. Math., 190 (2005), 343–359 | MR | Zbl

[10] Kapovich I., Myasnikov A. G., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264 (2003), 665–694 | MR | Zbl

[11] Kapovich I., Rivin I., Schupp P., Shpilrain V., “Densities in free groups and $\mathbb{Z}^k$, visible points and test elements”, Math. Res. Lett., 14 (2007), 263–284 | MR | Zbl

[12] Kapovich I., Rivin I., Schupp P., Shpilrain V., “Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups”, Pacific J. Math., 223 (2006), 113–140 | MR | Zbl

[13] Myasnikov A., Roman'kov V., Ushakov A., Vershik A., “The word and geodesic problems in free solvable groups”, Trans. Amer. Math. Soc., 362 (2010), 4655–4682 | MR | Zbl

[14] Myasnikov A. G., Shpilrain V., Ushakov A., Non-Commutative Cryptography and Complexity of Group-Theoretic Problems, Math. Surveys Monographs, 177, Amer. Math. Soc., Providence, 2011 | MR | Zbl

[15] Rivin I., “How to pick a random integer matrix? (and other questions)”, Math. Comput., 85 (2016), 783–797 | MR | Zbl

[16] Shpilrain V., “Sublinear time algorithms in the theory of groups and semigroups”, Illinois J. Math., 54 (2011), 187–197 | MR

[17] Tao T., Topics in Random Matrix Theory, Grad. Stud. Math., 132, Amer. Math. Soc., Providence, 2012 | MR | Zbl