CGC Bulletin 32
CGC Bulletin 32
Contents:
- Generic Computability, Turing Reducibility and Asymptotic Density
- Authentication from matrix conjugation
- Space functions of groups
- On the conjugacy problem for finite-state automorphisms of regular rooted trees
- Group extensions over infinite words
- Nielsen equivalence in small cancellation groups
- Polynomial time conjugacy in wreath products and free solvable groups
- Asymptotic invariants, complexity of groups and related problems
- Algorithmically finite groups
- Examples of the Generalized Quantum Permanent Compromise Attack to the Blum-Micali Construction
- Knuth-Bendix algorithm and the conjugacy problems in monoids
- Symbolic Computations and Post-Quantum Cryptography Online Seminar
Regards,
Boaz Tsaban
Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html
1. Generic Computability, Turing Reducibility and Asymptotic Density
Carl G. Jockusch Jr. and Paul E. Schupp
Generic computability has been studied in group theory and we now study it in the context of classical computability theory. A set A of natural numbers is generically computable if there is a partial computable function f whose domain has density 1 and which agrees with the characteristic function of A on its domain. A set A is coarsely computable if there is a computable set C such that the symmetric difference of A and C has density 0. We prove that there is a c.e. set which is generically computable but not coarsely computable and vice versa. We show that every nonzero Turing degree contains a set which is not coarsely computable. We prove that there is a c.e. set of density 1 which has no computable subset of density 1. As a corollary, there is a generically computable set A such that no generic algorithm for A has computable domain. We define a general notion of generic reducibility in the spirt of Turing reducibility and show that there is a natural order-preserving embedding of the Turing degrees into the generic degrees which is not surjective.
http://arxiv.org/abs/1010.5212
2. Authentication from matrix conjugation
Dima Grigoriev and Vladimir Shpilrain
Journal-ref: Groups, Complexity, and Cryptology 1 (2009), 199--206
We propose an authentication scheme where forgery (a.k.a. impersonation) seems infeasible without finding the prover's long-term private key. The latter would follow from solving the conjugacy search problem in the platform (noncommutative) semigroup, i.e., to recovering X from X^{-1}AX and A. The platform semigroup that we suggest here is the semigroup of nxn matrices over truncated multivariable polynomials over a ring.
http://arxiv.org/abs/1010.5034
3. Space functions of groups
Alexander Olshanskiy
We consider space functions $s(n)$ of finitely presented groups $G =< A\mid R> .$ (These functions have a natural geometric analog.) To define $s(n)$ we start with a word $w$ over $A$ of length at most $n$ equal to 1 in $G$ and use relations from $R$ for elementary transformations to obtain the empty word; $s(n)$ bounds from above the tape space (or computer memory) one needs to transform any word of length at most $n$ vanishing in $G$ to the empty word. One of the main obtained results is the following criterion: A finitely generated group $H$ has decidable word problem of polynomial space complexity if and only if $H$ is a subgroup of a finitely presented group $G$ with a polynomial space function.
http://arxiv.org/abs/1011.0118
4. On the conjugacy problem for finite-state automorphisms of regular rooted trees Ievgen
V. Bondarenko, Natalia V. Bondarenko, Said N. Sidki, Flavia R. Zapata
We study the conjugacy problem in the automorphism group $Aut(T)$ of a regular rooted tree $T$ and in its subgroup $FAut(T)$ of finite-state automorphisms. We show that under the contracting condition and the finiteness of what we call the orbit-signalizer, two finite-state automorphisms are conjugate in $Aut(T)$ if and only if they are conjugate in $FAut(T)$, and that this problem is decidable. We prove that both these conditions are satisfied by bounded automorphisms and establish that the (simultaneous) conjugacy problem in the group of bounded automata is decidable.
http://arxiv.org/abs/1011.2227
5. Group extensions over infinite words
Volker Diekert, Alexei Myasnikov
We construct an extension $E(A,G)$ of a given group $G$ by infinite non-Archimedean words over an discretely ordered abelian group like $Z^n$. This yields an effective and uniform method to study various groups that "behave like $G$". We show that the Word Problem for f.g. subgroups in the extension is decidable if and only if and only if the Cyclic Membership Problem in $G$ is decidable.
The present paper embeds the partial monoid of infinite words as defined by Myasnikov, Remeslennikov, and Serbin (Contemp. Math., Amer. Math. Soc., 378:37-77, 2005) into $E(A,G)$. Moreover, we define the extension group $E(A,G)$ for arbitrary groups $G$ and not only for free groups as done in previous work. We show some structural results about the group (existence and type of torsion elements, generation by elements of order 2) and we show that some interesting HNN extensions of $G$ embed naturally in the larger group $E(A,G)$.
http://arxiv.org/abs/1011.2024
6. Nielsen equivalence in small cancellation groups
Ilya Kapovich and Richard Weidmann
Let $G$ be a group given by the presentation \[\langle a_1,...,a_k,b_1,...,b_k\,|\,a_i=u_i(\bar b), b_i=v_i(\bar a)\hbox{ for }1\le i\le k\rangle,\] where $k\ge 2$ and where the $u_i\in F(b_1,..., b_k)$ and $w_i\in F(a_1,..., a_k)$ are random words. Generically such a group is a small cancellation group and it is clear that $(a_1,...,a_k)$ and $(b_1,...,b_k)$ are generating $n$-tuples for $G$. We prove that for generic choices of $u_1,..., u_k$ and $v_1,..., v_k$ the ``once-stabilized'' tuples $(a_1,..., a_k,1)$ and $(b_1,...,b_k,1)$ are not Nielsen equivalent in $G$. This provides a counter-example for a Wiegold-type conjecture in the setting of word-hyperbolic groups. We conjecture that in the above construction at least $k$ stabilizations are needed to make the tuples $(a_1,..., a_k)$ and $(b_1,...,b_k)$ Nielsen equivalent.
http://arxiv.org/abs/1011.5862
7. Polynomial time conjugacy in wreath products and free solvable groups
Svetla Vassileva
We prove that the complexity of the Conjugacy Problems for wreath products and for free solvable groups is decidable in polynomial time. For the wreath product AwrB, we must assume the decidability in polynomial time of the Conjugacy Problems for A and B and of the power problem in B. We obtain the result by making the algorithm for the Conjugacy Problem described in a paper of Matthews run in polynomial time. Using this result and properties of the Magnus embedding, we show that the Conjugacy and Conjugacy Search Problems in free solvable groups are computable in polynomial time.
http://arxiv.org/abs/1011.5931
8. Asymptotic invariants, complexity of groups and related problems
Mark Sapir
We survey results about computational complexity of the word problem in groups, Dehn functions of groups and related problems.
http://arxiv.org/abs/1012.1325
9. Algorithmically finite groups
A. Myasnikov, D. Osin
We call a group $G$ {\it algorithmically finite} if no algorithm can produce an infinite set of pairwise distinct elements of $G$. We construct examples of recursively presented infinite algorithmically finite groups and study their properties. For instance, we show that the Equality Problem is decidable in our groups only on strongly (exponentially) negligible sets of inputs.
10. Examples of the Generalized Quantum Permanent Compromise Attack to the Blum-Micali Construction
Ello\'a B. Guedes and Francisco Marcos de Assis and Bernardo Lula Jr
This paper presents examples of the quantum permanent compromise attack tothe Blum-Micali construction. Such attacks illustrate how a previous attack tothe Blum-Micali generator can be extended to the whole Blum-Micaliconstruction, including the Blum-Blum-Shub and Kaliski generators.
11. Knuth-Bendix algorithm and the conjugacy problems in monoids
Fabienne Chouraqui
We present an algorithmic approach to the conjugacy problems in monoids, using rewriting systems. We extend the classical theory of rewriting developedby Knuth and Bendix to a rewriting that takes into account the cyclicconjugates.
To appear in _Semigroup forum_
http://arxiv.org/abs/1012.3547
12. Symbolic Computations and Post-Quantum Cryptography Online Seminar
Dear colleagues,
As some of you already know, we are launching a new online seminardedicated to symbolic computations and applications to cryptography.
The first talk is scheduled on January 19, 2011.
Complete information can be found here:
http://www.stevens.edu/algebraic/SCPQ/
I would like to ask you to help to advertise the seminar. Please submit an announcement to your favorite mailing list, digest, database or just print the webpage and post it at your department.
There is a mailing list:
https://lists.stevens.edu/cgi-bin/mailman/listinfo/scpqwebinar
It will be used to send announcements regarding the seminar. Everyone interested in the seminar should subscribe to the list.
Thank you for your help.
Sincerely,
Alex Myasnikov
---
END OF ISSUE
