CGC Bulletin 34 =============== Contents: 1. Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P 2. The Finitary Andrews-Curtis Conjecture 3. The center of pure complex braid groups 4. Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems 5. Groups with undecidable word problem and almost quadratic Dehn function 6. Journal of Mathematical Cryptology April 2011, Vol. 4, No. 4 7. Twisted conjugacy in braid groups 8. Public Key Protocol Based on Amalgamated Free Product 9. On the cryptanalysis of the generalized simultaneous conjugacy search problem and the security of the Algebraic Eraser 10. Random equations in nilpotent groups 12. Dual Garside structure and reducibility of braids 13. Presentations for the higher dimensional Thompson's groups nV 14. D-Wave Sells First Quantum Computer Regards, Boaz Tsaban Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html Remark: Papers announced here are not checked for correctness. Readers finding a paper announced here incorrect or problematic, are kindly requested to inform me. --- 1. Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P Volker Diekert, J\"urn Laun, Alexander Ushakov Power circuits are data structures which support efficient algorithms for highly compressed integers. Using this new data structure it has been shown recently by Myasnikov, Ushakov and Won that the Word Problem of the one-relator Baumslag group is in P. Before that the best known upper bound has been non-elementary. In the present paper we provide new results for power circuits and we give new applications in algorithmic algebra and algorithmic group theory: 1. We define a modified reduction procedure on power circuits which runs in quadratic time thereby improving the known cubic time complexity. The improvement is crucial for our other results. 2. We improve the complexity of the Word Problem for the Baumslag group to cubic time thereby providing the first practical algorithm for that problem. 3. The main result is that the Word Problem of Higman's group is decidable in polynomial time. The situation for Higman's group is more complicated than for the Baumslag group and forced us to advance the theory of power circuits. http://arxiv.org/abs/1103.1232 --- 2. The Finitary Andrews-Curtis Conjecture Alexandre V. Borovik, Alexander Lubotzky and Alexei G. Myasnikov Appeared in Progress in Mathematics, Vol. 248, 15-30. 2005 Birkh\"auser Verlag Basel/Switzerland The well known Andrews-Curtis Conjecture [2] is still open. In this paper, we establish its finite version by describing precisely the connected components of the Andrews-Curtis graphs of finite groups. This finite version has independent importance for computational group theory. It also resolves a question asked in [5] and shows that a computation in finite groups cannot lead to a counterexample to the classical conjecture, as suggested in [5]. http://arxiv.org/abs/1103.1295 --- 3. The center of pure complex braid groups Fran\c{c}ois Digne (LAMFA), Ivan Marin (IMJ), Jean Michel (IMJ) Brou\'e, Malle and Rouquier conjectured in that the center of the pure braid group of an irreducible finite complex reflection group is cyclic. We prove this conjecture, for the remaining exceptional types, using the analogous result for the full braid group due to Bessis, and we actually prove the stronger statement that any finite index subgroup of such braid group has cyclic center. http://arxiv.org/abs/1103.2898 --- 4. Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems Benjamin Fine, Maggie Habeeb, Delaram Kahrobaei, Gerhard Rosenberger Most common public key cryptosystems and public key exchange protocols presently in use, such as the RSA algorithm, Diffie-Hellman, and elliptic curve methods are number theory based and hence depend on the structure of abelian groups. The strength of computing machinery has made these techniques theoretically susceptible to attack and hence recently there has been an active line of research to develop cryptosystems and key exchange protocols using noncommutative cryptographic platforms. This line of investigation has been given the broad title of noncommutative algebraic cryptography. This was initiated by two public key protocols that used the braid groups, one by Ko, Lee et.al.and one by Anshel, Anshel and Goldfeld. The study of these protocols and the group theory surrounding them has had a large effect on research in infinite group theory. In this paper we survey these noncommutative group based methods and discuss several ideas in abstract infinite group theory that have arisen from them. We then present a set of open problems. http://arxiv.org/abs/1103.4093 --- 5. Groups with undecidable word problem and almost quadratic Dehn function A.Yu. Olshanskii We construct a finitely presented group with undecidable word problem and with Dehn function bounded by a quadratic function on an infinite set of positive integers. http://arxiv.org/abs/1104.1476 --- 6. Journal of Mathematical Cryptology April 2011, Vol. 4, No. 4 Nonsmooth cryptanalysis, with an application to the stream cipher MICKEY Elmar Tischhauser Poly-Dragon: an efficient multivariate public key cryptosystem Rajesh P. Singh, A. Saikia, and B. K. Sarma Cryptanalysing variants of Stickel's key agreement scheme Ciaran Mullan Equivalent keys in ultivariate uadratic public key systems Christopher Wolf and Bart Preneel http://www.reference-global.com/toc/jmc/2011/4/4?ai=10i&ui=ng6&af=H --- 7. Twisted conjugacy in braid groups Juan Gonz\'alez-Meneses and Enric Ventura In this note we solve the twisted conjugacy problem for braid groups, i.e. we propose an algorithm which, given two braids $u,v\in B_n$ and an automorphism $\phi \in Aut (B_n)$, decides whether $v=(\phi (x))^{-1}ux$ for some $x\in B_n$. As a corollary, we deduce that each group of the form $B_n \rtimes H$, a semidirect product of the braid group $B_n$ by a torsion-free hyperbolic group $H$, has solvable conjugacy problem. http://arxiv.org/abs/1104.5690 --- 8. Public Key Protocol Based on Amalgamated Free Product Sumit Kumar Upadhyay, Shiv Datt Kumar and Ramji Lal In the spirit of Diffie Hellman the concept of a protocol algebra is introduced using certain amalgamated free product of Braid group B and Thompson group T together with a nilpotent subgroup H of index 2. http://arxiv.org/abs/1105.1086 --- 9. On the cryptanalysis of the generalized simultaneous conjugacy search problem and the security of the Algebraic Eraser Paul E. Gunnells The Algebraic Eraser (AE) is a cryptographic primitive that can be used to obscure information in certain algebraic cryptosystems. The Colored Burau Key Agreement Protocol (CBKAP), which is built on the AE, was introduced by I. Anshel, M. Anshel, D. Goldfeld, and S. Lemieux in 2006 as a protocol suitable for use on platforms with constrained computational resources, such as RFID and wireless sensors. In 2009 A. Myasnikov and A. Ushnakov proposed an attack on CBKAP that attempts to defeat the generalized simultaneous conjugacy search problem, which is the public-key computational problem underlying CBKAP. In this paper we investigate the effectiveness of this attack. Our findings are that success of the attack only comes from applying it to short keys, and that with appropriate keys the attack fails in 100% of cases and does not pose a threat against CBKAP. Moreover, the attack makes assumptions about CBKAP that do not hold in practical implementations, and thus does not represent a threat to the use of CBKAP in applications. http://arxiv.org/abs/1105.1141 Editor's note: Cf. http://arxiv.org/abs/0804.0629 --- 10. Random equations in nilpotent groups Robert Gilman, Alexei Myasnikov and Vitalii Romankov In this paper we study satisfiability of random equations in an infinite finitely generated nilpotent group G. We show that the set SAT(G,k) of all equations in k > 1 variables over G which are satisfiable in G has an intermediate asymptotic density in the space of all equations in k variables over G. When G is a free abelian group of finite rank, we compute this density precisely; otherwise we give some non-trivial upper and lower bounds. For k = 1 the set SAT(G,k) is negligible. Usually the asymptotic densities of interesting sets in groups are either zero or one. The results of this paper provide new examples of algebraically significant sets of intermediate asymptotic density. http://arxiv.org/abs/1105.2234 --- 11. Sublinear time algorithms in the theory of groups and semigroups Vladimir Shpilrain Sublinear time algorithms represent a new paradigm in computing, where an algorithm must give some sort of an answer after inspecting only a small portion of the input. The most typical situation where sublinear time algorithms are considered is property testing. There are several interesting contexts where one can test properties in sublinear time. A canonical example is graph colorability. To tell that a given graph is not k-colorable, it is often sufficient to inspect just one vertex with incident edges: if the degree of a vertex is greater than k, then the graph is not k-colorable. It is a challenging and interesting task to find algebraic properties that could be tested in sublinear time. In this paper, we address several algorithmic problems in the theory of groups and semigroups that may admit sublinear time solution, at least for "most" inputs. http://arxiv.org/abs/1105.3252 --- 12. Dual Garside structure and reducibility of braids Matthieu Calvez Benardete, Gutierrez and Nitecki showed an important result which relates the geometrical properties of a braid, as a homeomorphism of the punctured disk, to its algebraic Garside-theoretical properties. Namely, they showed that if a braid sends a curve to another curve, then the image of this curve after each factor of the left normal form of the braid (with the classical Garside structure) is also standard. We provide a new simple, geometric proof of the result by Benardete-Gutierrez-Nitecki, which can be easily adapted to the case of the dual Garside structure of braid groups, with the appropriate definition of standard curves in the dual setting. This yields a new algorithm for determining the Nielsen-Thurston type of braids. http://arxiv.org/abs/1105.3675 --- 13. Presentations for the higher dimensional Thompson's groups nV Johanna Hennig, Francesco Matucci In his papers [2], [3] Brin introduced the higher dimensional Thompson groups nV which are generalizations to the Thompson's group V of self-homeomorphisms of the Cantor set and found a finite set of generators and relations in the case n = 2. We show how to generalize his construction to obtain a finite presentation for every positive integer n. As a corollary, we obtain another proof that the groups nV are simple (first proved by Brin in [4]). http://arxiv.org/abs/1105.3714 --- 14. D-Wave Sells First Quantum Computer D-Wave Systems made history by announcing the sale of the world's first commercial quantum computer. The buyer was Lockheed Martin Corporation, who will use the machine to help solve some of their "most challenging computation problems." Lockheed purchased the system, known as D-Wave One, as well as maintenance and associated professional services. Terms of the deal were not disclosed. http://www.hpcwire.com/hpcwire/2011-05-26/d-wave_sells_first_quantum_computer.html --- END OF ISSUE