Complexity and Randomness in Group Theory
by Frédérique Bassino (Author), Ilya Kapovich (Author), Markus Lohrey (Author), Alexei Miasnikov (Author), Cyril Nicaud (Author)

About this Book
This book shows new directions in group theory motivated by computer science. It reflects the transition from geometric group theory to group theory of the 21st century that has strong connections to computer science. Now that geometric group theory is drifting further and further away from group theory to geometry, it is natural to look for new tools and new directions in group theory which are present.

Brief Contents
1 Generic-case complexity in group theory | 1
    1.1 Introduction | 1
    1.2 Definition(s) of generic-case complexity | 4
    1.3 Decision problems in group theory: general set-up | 10
    1.4 Quotient test methods | 11
    1.5 Generic-case complexity of “search” group-theoretic problems | 23
    1.6 Algorithmically finite groups | 28
    1.7 Whitehead algorithm and related problems | 30
    1.8 Generic-case complexity of the isomorphism problem | 38
2 Random presentations and random subgroups | 45
    2.1 Introduction | 45
    2.2 Random finite presentations | 48
    2.3 Random subgroups | 61
    2.4 Nonuniform distributions | 71
3 Randomness and computation in linear groups | 77
    3.1 What is a random element of an infinite matrix group? | 77
    3.2 Properties of generic elements | 80
    3.3 Random walks on groups and graphs | 84
    3.4 Fourier transform on finite groups | 85
    3.5 Fourier estimates via linear algebra | 87
    3.6 Some remarks on matrix norms | 89
    3.7 Properties of random subgroups | 90
    3.8 Subgroups of SL2(ℤ) | 92
    3.9 Subgroups of SLn(ℤ) for n > 2 | 97
    3.10 Well-roundedness | 109
    3.11 Lyapunov exponent estimates | 112
    3.12 How to pick a random element? | 114
    3.13 Geometric preliminaries | 115
    3.14 Action of SL(2,ℝ) and SL(2,ℤ) on the upper half-plane | 117
    3.15 Selecting a random element of SL(2,ℤ) almost uniformly | 120
    3.16 Extensions to other Fuchsian and Kleinian groups | 122
    3.17 Higher rank | 123
    3.18 Miscellaneous other groups | 125
    3.19 Checking Zariski density | 129
    3.20 Algorithms for large Galois groups | 131
    3.21 Probabilistic algorithms | 133
    3.22 Probabilistic algorithm to check if p(x) of degree n has Galois group Sn | 134
    3.23 Back to Zariski density | 138
    3.24 A short history of Galois group algorithms | 139
    3.25 Some lemmas on permutations | 143
    3.26 A bit about polynomials | 146
    3.27 The Frobenius density theorem | 146
    3.28 Another Zariski density algorithm | 148
    3.29 The base case: rank 1 | 149
    3.30 Higher rank | 150
    3.31 Thin or not? | 150
4 Compression techniques in group theory | 155
    4.1 Introduction | 155
    4.2 General notations | 158
    4.3 Background from complexity theory | 159
    4.4 Rewrite systems | 162
    4.5 Groups and the word problem | 163
    4.6 Exponential compression | 168
    4.7 Tower compression and beyond | 199
    4.8 Open problems | 220
5 Discrete optimization in groups | 223
    5.1 Introduction | 223
    5.2 Subset sum problem and related problems | 246
    5.3 Knapsack problem | 271
    5.4 Post correspondence problem | 291
6 Problems in group theory motivated by cryptography | 317
    6.1 Introduction | 317
    6.2 The Diffie–Hellman key exchange protocol | 318
    6.3 The conjugacy problem | 320
    6.4 The decomposition problem | 324
    6.5 The word problem | 328
    6.6 The subgroup membership problem | 332
    6.7 Using the subgroup membership decision problem | 334
    6.8 The isomorphism inversion problem | 335
    6.9 Semidirect product of groups and more peculiar computational assumptions | 339
    6.10 The subset sum problem and the knapsack problem | 342
    6.11 The hidden subgroup problem | 344
    6.12 Relations between some of the problems | 345
Bibliography | 349
Index | 371

Pages : 450
ISBN-13 : 978-3110664911
ISBN-10 : 3110664917
Publisher : De Gruyter (June 8, 2020)
Language : English