BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Alexei Myasnikov appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We show that the Diophantine problem(decidability of equations) is undecidable in free associative algebras over any field and in the group algebras over any field of a wide variety of torsion free groups, including toral relatively hyperbolic groups, right angled Artin groups, commutative transitive groups, the fundamental groups of various graph groups, etc.
We consider several subgroup-related algorithmic questions in groups, modeled after the classic computational lattice problems, and study their computational complexity. We find polynomial time solutions to problems like finding a subgroup element closest to a given group element, or finding a shortest non-trivial element of a subgroup in the case of nilpotent groups, and a large class of surface groups and Coxeter groups. We also provide polynomial time algorithm to compute geodesics in given generators of a subgroup of a free group.
We discuss a new attack, termed a dimension or linear decomposition attack, on several known group-based cryptosystems. This attack gives a polynomial time deterministic algorithm that recovers the secret shared key from the public data in all this schemes under consideration. Furthemore, we show that in this case, contrary to the common opinion, the typical computational security assumptions are not very relevant to the security of the schemes, i.e., one can break the schemes without solving the algorithmic problems on which the assumptions are based. The efficacy of the attack depends on the platform group, so it requires a more thorough analysis in each particular case.
This note provides a brief guide to the current state of the literature on Tarski's problems with emphasis on features that distinguish the approach based on combinatorial and algorithmic group theory from the topological approach to Tarski's problem. We use this note to provide corrections to some typos and to address some misconceptions from the recent report by Z. Sela about the relations between the concepts and results in the approaches to the Tarski problems. We were forced to read Sela's papers to be able to address some of his comments, and found errors in his papers 6, 3 and 4 on Diophantine Geometry published in GAFA and Israel J. Math. which we mention in Section 4. His proceedings of the ICM 2002 paper also contains wrong Theorem 6 (to make it correct one has to change the definition of non-elementary hyperbolic $ω$-residually free towers to make them equivalent to our coordinate groups of regular NTQ systems.)
Let $G$ be a non-elementary hyperbolic group. Let $w$ be a group word such that the set $w[G]$ of all its values in $G$ does not coincide with $G$ or 1. We show that the width of verbal subgroup $w(G)=<w[G]>$ is infinite. That is, there is no such $l\in\mathbb Z$ that any $g\in w(G)$ can be represented as a product of $\le l$ values of $w$ and their inverses.
In this paper we survey recent developments in the theory of groups acting on $Λ$-trees. We are trying to unify all significant methods and techniques, both classical and recently developed, in an attempt to present various faces of the theory and to show how these methods can be used to solve major problems about finitely presented $Λ$-free groups. Besides surveying results known up to date we draw many new corollaries concerning structural and algorithmic properties of such groups.
We generalize the classical knapsack and subset sum problems to arbitrary groups and study the computational complexity of these new problems. We show that these problems, as well as the bounded submonoid membership problem, are P-time decidable in hyperbolic groups and give various examples of finitely presented groups where the subset sum problem is NP-complete.
We generalize the classical Post correspondence problem ($\mathbf{PCP}_n$) and its non-homogeneous variation ($\mathbf{GPCP}_n$) to non-commutative groups and study the computational complexity of these new problems. We observe that $\mathbf{PCP}_n$ is closely related to the equalizer problem in groups, while $\mathbf{GPCP}_n$ is connected to the double twisted conjugacy problem for endomorphisms. Furthermore, it is shown that one of the strongest forms of the word problem in a group $G$ (we call it the {\em hereditary word problem}) can be reduced to $\mathbf{GPCP}_n$ in $G$ in polynomial time. The main results are that $\mathbf{PCP}_n$ is decidable in a finitely generated nilpotent group in polynomial time, while $\mathbf{GPCP}_n$ is undecidable in any group containing free non-abelian subgroup (though the argument is very different from the classical case of free semigroups). We show that the double endomorphism twisted conjugacy problem is undecidable in free groups of sufficiently large finite rank. We also consider the bounded $\mathbf{PCP}$ and observe that it is in $\mathbf{NP}$ for any group with $\mathbf{P}$-time decidable word problem, meanwhile it is $\mathbf{NP}$-hard in any group containing free non-abelian subgroup. In particular, the bounded $\mathbf{PCP}$ is $\mathbf{NP}$-complete in non-elementary hyperbolic groups and non-abelian right angle Artin groups.
Cyclic words are equivalence classes of cyclic permutations of ordinary words. When a group is given by a rewriting relation, a rewriting system on cyclic words is induced, which is used to construct algorithms to find minimal length elements of conjugacy classes in the group. These techniques are applied to the universal groups of Stallings pregroups and in particular to free products with amalgamation, HNN-extensions and virtually free groups, to yield simple and intuitive algorithms and proofs of conjugacy criteria.
We give a description of definable sets $P=(p_1,..., p_m)$ in a free non-abelian group $F$ and in a torsion-free non-elementary hyperbolic group $G$ that follows from our work on the Tarski problems. This answers Malcev's question for $F$. As a corollary we show that proper non-cyclic subgroups of $F$ and $G$ are not definable and prove Bestvina and Feighn's result that definable subsets $P=(p)$ in a free group are either negligible or co-negligible in their terminology.
We provide polynomial upper bounds on the size of a shortest solution for quadratic equations in a free group. A similar bound is given for parametric solutions in the description of solutions sets of quadratic equations in a free group.
In this paper we introduce elements of algebraic geometry over an arbitrary algebraic structure. We prove Unification Theorems which gather the description of coordinate algebras by several ways.
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)$.
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.
In this paper we discuss some special generalizations of equationally Noetherian property which naturally arise in the universal algebraic geometry. We introduce weakly equationally Noetherian, qw-compact, uw-compact, and weakly uw-compact algebras and then examine properties of such algebras. Also we consider the connections between five classes: the class of equationally Noetherian algebras, the class of weakly equationally Noetherian algebras, the class of uw-compact algebras, the class of weakly uw-compact algebras, and the class of qw-compact algebras.
In this paper we prove Implicit Function Theorems (IFT) for algebraic varieties defined by regular quadratic equations and, more generally, regular NTQ systems over free groups. In the model theoretic language these results state the existence of very simple Skolem functions for particular $\forall\exists$-formulas over free groups. We construct these functions effectively. In non-effective form IFT first appeared in \cite{Imp}. From algebraic geometry view-point IFT can be described as lifting solutions of equations into generic points of algebraic varieties. Moreover, we show that the converse is also true, i.e., IFT holds only for algebraic varieties defined by regular NTQ systems. This implies that if a finitely generated group $H$ is $\forall\exists$-equivalent to a free non-abelian group then $H$ is isomorphic to the coordinate group of a regular NTQ system.