BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let O be the ring of integers of a number field, and let n≥3. This paper studies bi-interpretability of the ring of integers Z with the special linear group SLn(O), the general linear group GLn(O) and solvable group of all invertible uppertriangular matrices over O, Tn(O). For each of these groups we provide a complete characterization of arbitrary models of their complete elementary theories.
In this paper we study the algebraic structure of ω-stable bilinear maps, arbitrary rings and nilpotent groups. We will also provide rather complete structure theorems for the above structures in the finite Morley rank case.
In various occasions the conjugacy problem in finitely generated amalgamated products and HNN extensions can be decided efficiently for elements which cannot be conjugated into the base groups. This observation asks for a bound on how many such elements there are. Such bounds can be derived using the theory of amenable graphs: In this work we examine Schreier graphs of amalgamated products and HNN extensions. For an amalgamated product G=H∗AK with [H:A]≥[K:A]≥2, the Schreier graph with respect to H or K turns out to be non-amenable if and only if [H:A]≥3. Moreover, for an HNN extension of the form G=<H,b∣bab−1=ϕ(a),a∈A>, we show that the Schreier graph of G with respect to the subgroup H is non-amenable if and only if A=H=ϕ(A). As application of these characterizations we show that under certain conditions the conjugacy problem in fundamental groups of finite graphs of groups with free abelian vertex groups can be solved in polynomial time on a strongly generic set. Furthermore, the conjugacy problem in groups with more than one end can be solved with a strongly generic algorithm which has essentially the same time complexity as the word problem. These are rather striking results as the word problem might be easy, but the conjugacy problem might be even undecidable. Finally, our results yield another proof that the set where the conjugacy problem of the Baumslag group is decidable in polynomial time is also strongly generic.
In this paper we study distortion of various well-known embeddings of finitely generated torsion-free nilpotent groups G into unitriangular groups UTn(Z). We also provide a polynomial time algorithm for finding distortion of a given subgroup of G
Let G=CA∗B be an amalgamated product of finite rank free groups A, B and C. We introduce atomic measures and corresponding asymptotic densities on a set of normal forms of elements in G. We also define two strata of normal forms: the first one consists of regular (or stable) normal forms, and second stratum is formed by singular (or unstable) normal forms. In a series of previous work about classical algorithmic problems, it was shown that standard algorithms work fast on elements of the first stratum and nothing is known about their work on the second stratum. In main theorems A and B of this paper we give probabilistic and asymptotic estimates of these strata.
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].
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.
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.