6 citations · 21 across the 30 of their papers we have counts for
4 papers · 1 filter
Orbit-blocking words and the average-case complexity of Whitehead's problem in the free group of rank 2
Lucy Hyde, Siobhan O'Connor, Vladimir Shpilrain
Let F_2 denote the free group of rank 2. Our main technical result of independent interest is: for any element u of F_2, there is g in F_2 such that no cyclically reduced image of…
Growth in products of matrices: fastest, average, and generic
Vladimir Shpilrain
The problems that we consider in this paper are as follows. Let A and B be 2x2 matrices (over reals). Let w(A, B) be a word of length n. After evaluating w(A, B) as a product of ma…
Cayley hashing with cookies
Vladimir Shpilrain, Bianca Sosnovski
Cayley hash functions are based on a simple idea of using a pair of semigroup elements, A and B, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in…
Complexity of some algorithmic problems in groups: a survey
Vladimir Shpilrain
In this survey, we address the worst-case, average-case, and generic-case time complexity of the word problem and some other algorithmic problems in several classes of groups and s…