CGC Bulletin 30

eZine lover (@eZine)

Published in 

CGC Bulletin

 · 9 months ago

Contents

1. Journal of Mathematical Cryptology, Vol. 3, No. 4
2. Artin groups of large type are shortlex automatic with regular geodesics
3. Simple Braids
4. On the difficulty of presenting finitely presentable groups
5. Fast algorithmic Nielsen-Thurston classification of four-strand braids
6. Groups, Complexity, and Cryptology joins Walter deGruyter
7. On certain permutation representations of the braid group. Part II
8. Nilpotent groups without exactly polynomial Dehn function
9. On the Conjugacy Problem in Groups and its Variants
10. Security Estimates for Quadratic Field Based Cryptosystems
11. Suzuki groups as expanders
12. Finding direct product decompositions in polynomial time
13. On reduction curves and Garside properties of braids
14. Power Circuits, Exponential Algebra, and Time Complexity
15. Groups elementarily equivalent to a free nilpotent group of finite rank
16. PSL(2,Z) as a non distorted subgroup of Thompson's group T

Regards,

Boaz Tsaban

Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html

1. Journal of Mathematical Cryptology, Vol. 3, No. 4

On a conjecture for balanced symmetric Boolean functions
Thomas W. Cusick, Yuan Li, and Pantelimon St?ni?

A recursive construction for perfect hash families
Charles J. Colbourn and Alan C. H. Ling

The Miller–Rabin test with randomized exponents
Gebhard B?ckle

Cryptanalysis of the MST3 public key cryptosystem
Simon R. Blackburn, Carlos Cid, and Ciaran Mullan

An efficient identification protocol secure against concurrent-reset attacks
J. Wu and D. R. Stinson

On hashing into elliptic curves
Reza R. Farashahi, Igor E. Shparlinski, and Jos? Felipe Voloch

http://www.reference-global.com/toc/jmc/2009/3/4?ai=10i&ui=ng6&af=H

2. Artin groups of large type are shortlex automatic with regular geodesics

Derek F Holt and Sarah Rees

We prove that any Artin group of large type is shortlex automatic with respect to its standard generating set, and that the set of all geodesic words over the same generating set satisfies the Falsification by Fellow-Traveller Property (FFTP) and hence is regular.

http://arxiv.org/abs/1003.6007

3. Simple Braids

Rehana Ashraf and Barbu Berceanu

We study a subset of square free positive braids and we give a few algebraic characterizations of them and one geometric characterization: the set of positive braids whose closures are unlinks. We describe canonical forms of these braids and of their conjugacy classes.

http://arxiv.org/abs/1003.6014

4. On the difficulty of presenting finitely presentable groups

Martin R Bridson and Henry Wilton

We provide the first examples of classes of groups in which the word problem is uniformly solvable but in which there is no algorithm that can compute finite presentations for finitely presentable subgroups. Direct products of hyperbolic groups, groups of integer matrices, and right-angled Coxeter groups form such classes. We discuss related classes of groups in which there does exist an algorithm to compute finite presentations for finitely presentable subgroups. We also construct a finitely presented group that has a polynomial Dehn function but in which there is no algorithm to compute the first Betti number of its finitely presentable subgroups.

http://arxiv.org/abs/1003.5117

5. Fast algorithmic Nielsen-Thurston classification of four-strand braids

Matthieu Calvez, Bert Wiest

We give an algorithm which decides the Nielsen-Thurston type of a given four-strand braid and whose complexity is quadratic with respect to word length.

http://arxiv.org/abs/1004.0067

6. Groups, Complexity, and Cryptology joins Walter deGruyter

The publication rights for the Groups, Complexity, and Cryptology journal have been transferred to Walter deGruyter.

New journal's webpage:

http://www.degruyter.de/journals/gcc/detailEn.cfm

Submissions to any member of the editorial board are welcome.

7. On certain permutation representations of the braid group. Part II

Valentin Vankov Iliev

In arXiv:0910.1727 we find certain finite homomorphic images of Artin braid group into appropriate symmetric groups, which a posteriori are extensions of the symmetric group on n letters by an abelian group. The main theorem of this paper characterizes completely the extensions of this type that are split.

http://arxiv.org/abs/1004.2811 , 4kb)

8. Nilpotent groups without exactly polynomial Dehn function

Stefan Wenger

We prove super-quadratic lower bounds for the growth of the filling area function of a certain class of Carnot groups. This class contains groups for which it is known that their Dehn function grows no faster than $n^2\log n$. We therefore obtain the existence of (finitely generated) nilpotent groups whose Dehn functions do not have exactly polynomial growth and we thus answer a well-known question about the possible growth rate of Dehn functions of nilpotent groups.

http://arxiv.org/abs/1004.2907

9. On the Conjugacy Problem in Groups and its Variants

Mich\`ele Feltz

This thesis deals with the conjugacy problem in groups and its twisted variants. We analyze recent results by Bogopolski, Martino, Maslakova and Ventura on the twisted conjugacy problem in free groups and its implication for the conjugacy problem in free-by-cyclic groups and some further group extensions. We also consider the doubly-twisted conjugacy problem in free groups. Staecker has developed an algorithm for deciding doubly-twisted conjugacy relations in the case where the involved homomorphisms satisfy a certain remnant inequality. We show how a similar condition affects the equalizer subgroup and raise new questions regarding this subgroup. As an application we discuss the Shpilrain-Ushakov authentication scheme based on the doubly-twisted conjugacy search problem in matrix semigroups over truncated polynomials over finite fields. Part of this thesis is devoted to the implementation and testing of some of the previously mentioned concepts in the GAP programming language.

http://arxiv.org/abs/1004.3588

10. Security Estimates for Quadratic Field Based Cryptosystems

Jean-Fran\c{c}ois Biasse (LIX, INRIA Bordeaux - Sud-Ouest), Jacobson John Michael (CPSC), Silverster K. Alan (CPSC)

Lecture notes in computer science (2010)

We describe implementations for solving the discrete logarithm problem in the class group of an imaginary quadratic field and in the infrastructure of a real quadratic field. The algorithms used incorporate improvements over previously-used algorithms, and extensive numerical results are presented demonstrating their efficiency. This data is used as the basis for extrapolations, used to provide recommendations for parameter sizes providing approximately the same level of security as block ciphers with $80,$ $112,$ $128,$ $192,$ and $256$-bit symmetric keys.

http://arxiv.org/abs/1004.5512

11. Suzuki groups as expanders

Emmanuel Breuillard, Ben Green, Terence Tao

We show that pairs of generators for the family Sz(q) of Suzuki groups may be selected so that the corresponding Cayley graphs are expanders. By combining this with several deep works of Kassabov, Lubotzky and Nikolov, this establishes that the family of all non-abelian finite simple groups can be made into expanders in a uniform fashion.

http://arxiv.org/abs/1005.0782

12. Finding direct product decompositions in polynomial time

James B. Wilson

A polynomial-time algorithm is produced which, given generators for a group of permutations on a finite set, returns a direct product decomposition of the group into directly indecomposable subgroups. The process uses bilinear maps and commutative rings to characterize direct products of p-groups of class 2 and reduces general groups to p-groups using group varieties. The methods apply to quotients of permutation groups and operator groups as well.

http://arxiv.org/abs/1005.0548

13. On reduction curves and Garside properties of braids

Juan Gonzalez-Meneses

In this paper we study the reduction curves of a braid, and how they can be used to decompose the braid into simpler ones in a precise way, which does not correspond exactly to the decomposition given by Thurston theory. Then we study how a cyclic sliding (which is a particular kind of conjugation) affects the normal form of a braid with respect to the normal forms of its components. Finally, using the above methods, we provide the example of a family of braids whose sets of sliding circuits (hence ultra summit sets) have exponential size with respect to the number of strands and also with respect to the canonical length.

http://arxiv.org/abs/1006.2258

14. Power Circuits, Exponential Algebra, and Time Complexity

Alexei G. Myasnikov, Alexander Ushakov, and Dong Wook Won

Motivated by algorithmic problems from combinatorial group theory we study computational properties of integers equipped with binary operations +, -, z = x 2^y, z = x 2^{-y} (the former two are partial) and predicates < and =. Notice that in this case very large numbers, which are obtained as n towers of exponentiation in the base 2 can be realized as n applications of the operation x2^y, so working with such numbers given in the usual binary expansions requires super exponential space. We define a new compressed representation for integers by power circuits (a particular type of straight-line programs) which is unique and easily computable, and show that the operations above can be performed in polynomial time if the numbers are presented by power circuits. We mention several applications of this technique to algorithmic problems, in particular, we prove that the quantifier-free theories of various exponential algebras are decidable in polynomial time, as well as the word problems in some "hard to crack" one-relator groups.

http://arxiv.org/abs/1006.2570

15. Groups elementarily equivalent to a free nilpotent group of finite rank

Alexei G. Myasnikov, Mahmood Sohrabi

In this paper we give a complete algebraic description of groups elementarily equivalent to a given free nilpotent group of finite rank.

http://arxiv.org/abs/1006.0290

16. PSL(2,Z) as a non distorted subgroup of Thompson's group T

Ariadna Fossas

In this paper we characterize the elements of PSL(2,Z), as a subgroup of Thompson group T, in the language of reduced tree pair diagrams and in terms of piecewise linear maps as well. Actually, we construct the reduced tree pair diagram for every element of PSL(2,Z) in normal form. This allows us to estimate the length of the elements of PSL(2,Z) through the number of carets of their reduced tree pair diagrams and, as a consequence, to prove that PSL(2,Z) is a non distorted subgroup of T. In particular, we find non-distorted free non abelian subgroups of T.

http://arxiv.org/abs/1006.0508

---

END OF ISSUE