33 citations · 63 across the 8 of their papers we have counts for
11 papers
Nonstandard free groups
Alexei Miasnikov, Andrey Nikolaev
Interpretation of a structure in allows to produce structures elementarily equivalent to given those elementarily equivalent to . In…
On subset sum problem in branch groups
Andrey Nikolaev, Alexander Ushakov
We consider a group-theoretic analogue of the classic subset sum problem. In this brief note, we show that the subset sum problem is NP-complete in the first Grigorchuk group. More…
Subset sum problem in polycyclic groups
Andrey Nikolaev, Alexander Ushakov
We consider a group-theoretic analogue of the classic subset sum problem. It is known that every virtually nilpotent group has polynomial time decidable subset sum problem. In this…
Non-commutative lattice problems
Alexei Myasnikov, Andrey Nikolaev, Alexander Ushakov
We consider several subgroup-related algorithmic questions in groups, modeled after the classic computational lattice problems, and study their computational complexity. We find po…
Logspace and compressed-word computations in nilpotent groups
Jeremy Macdonald, Alexei Myasnikov, Andrey Nikolaev +1
For finitely generated nilpotent groups, we employ Mal'cev coordinates to solve several classical algorithmic problems efficiently. Computation of normal forms, the membership prob…
Knapsack problems in products of groups
Elizaveta Frenkel, Andrey Nikolaev, Alexander Ushakov
The classic knapsack and related problems have natural generalizations to arbitrary (non-commutative) groups, collectively called knapsack-type problems in groups. We study the eff…
The Post correspondence problem in groups
Alexei Myasnikov, Andrey Nikolaev, Alexander Ushakov
We generalize the classical Post correspondence problem () and its non-homogeneous variation () to non-commutative groups and study the computation…
Knapsack Problems in Groups
Alexei Myasnikov, Andrey Nikolaev, Alexander Ushakov
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…
Membership Problem in groups acting freely on Z^n-trees
Andrey Nikolaev, Denis Serbin
Groups acting freely on Z^n-trees (Z^n-free groups) play a key role in the study of non-archimedean group actions. Following Stallings' ideas, we develop graph-theoretic techniques…
Verbal subgroups of hyperbolic groups have infinite width
Alexei Myasnikov, Andrey Nikolaev
Let be a non-elementary hyperbolic group. Let be a group word such that the set of all its values in does not coincide with or 1. We show that the width of v…
Finite index subgroups of fully residually free groups
Andrey Nikolaev, Denis Serbin
Using graph-theoretic techniques for f.g. subgroups of we provide a criterion for a f.g. subgroup of a f.g. fully residually free group to be of finite index. M…