2005 | 2004 | 2003 | 2002 | 2001 | 2000 | 1999 | 1998 | 1997 | 1996 | 1995 and earlier

 

 

2005

 

           Fully residually free groups and graphs labeled by infinite words (with  V. Remeslennikov and D. Serbin), to appear in Internat. J. Algebra and Comput.

 

           A practical attack on some braid group based cryptographic protocols (with V. Shpilrain

           and A. Ushakov). CRYPTO 2005, Lecture Notes Comp. Sci, 3621 (2005), 86-96.

 

On positive theories of groups with regular length functions (with B. Khan and D. Serbin).

 

Algebraic geometry over groups III: Elements of model theory (with A. Kvaschuk and

V.  Remeslennikov). J. of Algebra, 288 (2005), no. 1, 78-98. [.pdf]

 

Finitary Andrews-Curtis conjecture (with A.V. Borovik and A. Lubotzky), submitted.

[.pdf]

We formulate a generalized AC-conjecture for an arbitrary group and prove that it holds for  

every finite group. In fact, there are no counter examples to the generalized AC conjecture

so far. Such examples would shed some light on potential counterexamples to the original AC

conjecture.

 

            Pattern Recognition and Minimal Words in Free Groups of Rank 2 (with Robert M.

Haralick and Alexei D. Miasnikov), submitted. [.pdf]

We describe a linear time probabilistic algorithm to recognize Whitehead minimal elements (elements

of minimal length in their automorphic orbits) in free groups of rank 2. Moreover, for a non-minimal element the algorithm gives an automorphism that will most likely reduce the length of the element.

This method is based on linear regression and pattern recognition techniques. I did not believe this myself first, until I've seen it working with my own eyes.

 

Effective JSJ decompositions (with O. Kharlampovich), Contemp. Math., 378,  Amer.

Math. Soc., Providence,RI, 2005, 87-212. [.pdf]

 

Regular free length functions on Lyndon's free Z[t]-group F^Z[t] (with V. Remeslennikov

and D. Serbin), Contemp. Math., 378,  Amer. Math. Soc., Providence, RI, 2005, 37-77. [.pdf]

 

The conjugacy problem in amalgamated products I: regular elements and black holes

(with A. Borovik and V. Remeslennikov). Preprint.

 

The conjugacy problem in amalgamated products II: generic complexity (with A. Borovik

and V. Remeslennikov). Preprint.

 

Big powers and free constructions (with A. Kvaschuk), submitted.

 

Algorithmic stratification of the conjugacy problem in Miller’s groups  (with A. Borovik and V. Remeslennikov). Preprint. [.pdf]

 

Groups whose universal theory is axiomatizable by quasi-identities (with B. Fine,

A.M. Gaglione and D. Spellman), to appear in J. of Group Theory.

 

           Algebraic geometry over free groups: lifting solutions into generic points (with O.

           Kharlampovich), Contemp. Math., 378,  Amer. Math. Soc., Providence, RI, 2005, 213-318.

           [.pdf]

 

           Implicit function theorems over free groups (with O. Kharlampovich). J. of Algebra, 290

(2005), no. 1, 1-203. [.pdf]

 

Quotient tests and Gröbner bases (with M. Kreuzer, G. Rosenberger and A. Ushakov),

submitted. [.pdf]

 

The halting problem is almost always decidable (with J. Hamkins), Preprint. [.pdf]

 

Quotient tests and random walks in computational group theory (with A. Borovik),    

submitted. [.pdf]

 

The conjugacy problem in HNN-extensions I: regular elements, black holes and generic

complexity (with A. Borovik and V. Remeslennikov). Preprint.

 

Isomorphism problem for finitely generated fully residually free groups (with I.  

Bumagin and O.  Kharlampovich), submitted.[.pdf]

 

Exponential extensions of groups (with O. Kharlampovich, V. Remeslennikov and D.

Serbin), to appear in J. of Group Theory. [.pdf]

 

One variable equations over hyperbolic groups (with A. Kvaschuk). Preprint.

 

On the Hanna Newmann Conjecture (with T.Jitsukawa and B.Khan). Preprint. [.pdf]

 

Elementary theory of free non-abelian groups. The Tarski problem. (with

O. Kharlampovich). Preprint.

 

Heuristics for Whitehead Minimization Problem (with R.M. Haralick and A.D.

Miasnikov). Preprint.

 

Theorems on hierarchy in generalized recursion theory (with V. Belyaev). Preprint.

 

Average-case complexity and decision problems in group theory (with

I. Kapovich, P. Schupp and V. Shpilrain), Adv. Math. 190 (2005), no.2, 190-205. [.pdf]

 

Foldings, graphs of groups and the membership problem (with I.Kapovich and

R.Weidmann), Internat. J. Algebra Comput. 13 (2005), no. 1, 95-128.  [.pdf]

 

2004

 

Subgroups of fully residually free groups: algorithmic problems (with O. Kharlampovich, V. Remeslennikov and D. Serbin). Group theory, statistics, and cryptography, 63-101, Contemp. Math., 360, Amer. Math. Soc., Providence, RI, 2004. [.pdf]

 

Pattern Recognition Approaches to Solving Combinatorial Problems in Free Groups

(with Robert M. Haralick and Alexei D. Miasnikov), Contemp. Math., 349, Amer. Math. Soc., Providence, RI, 2004, 197-213. [.pdf]

In this survey paper we present some pattern recognition techniques that can be used in studying

free groups. As an illustration we apply these methods to Whitehead minimization problem.

 

Whitehead method and Genetic Algorithms (with Alexei D. Miasnikov) Contemp.

Math., 349, Amer. Math. Soc., Providence, RI, 2004, 89-114. [.pdf]

We describe a genetic Whitehead's algorithm for finding minimal elements (elements of  minimal length

in automorphic orbits) in arbitrary free groups. The classical Whitehead's algorithm is extremely

inefective for free groups of big ranks, but this genetic version of it works all right. Also we formulate

several mathematical conjectures that came out of our experiments.

 

Discriminating and co-discriminating groups (with P. Shumyatsky). J.  Group Theory 7

(2004), no. 1, 135-142. [.pdf]

 

One Variable Equations in free groups via context free languages (with R. Gilman).

Computational and experimental group theory, 83-88, Contemp. Math., 349, Amer. Math. 

 Soc., Providence, RI, 2004. [.pdf]

 

2003

 

Elementary theory of free groups (with B.Fine, A.M.Gaglione and D.Spellman), Proc.

Of  the Oxford/St. Andrews Conf. on Combinatorial Group Theory, London Math. Soc. Lect. 

Note Ser. 304 (2003), 197-231.

 

Multiplicative measures on free groups (with A. Borovik and V. Remeslennikov).

Internat. J. Algebra Comput. 13 (2003), no. 6, 705-731. [.pdf]

 

The Andrews-Curtis Conjecture and Black Box Groups (with A.V. Borovik and E.I.    

Khukhro). Internat. J. Algebra Comput., 13 (2003), no. 4, 415-436. [.pdf]

We introduce Andrews-Curtis graphs of groups and discuss their connection with black-box 

groups and the replacement algorithm, study AC conjecture for finite groups, and describe

possible attacks on AC conjecture via finite groups.

 

Automorphic orbits in free groups (with V.Shpilrain). J. of Algebra, 269 (2003), no. 1,

18-27. [.pdf]

 

Generic-case complexity and decision problems in group theory (with I. Kapovich, P.

Schupp and V.Shpilrain). J. of Algebra, 264 (2003), 665-694. [.pdf]

 

2002

 

Discriminating completions of hyperbolic groups (with G. Baumslag and V.  Remeslennikov). Geom. Dedicata 92 (2002), 115-143. [.pdf]

 

Measuring sets in infinite groups (with A. Borovik and V. Shpilrain). Computational and

statistical group theory (Las Vegas, NV/Hoboken, NJ, 2001), 21-42, Contemp. Math., 298,

 Amer. Math. Soc., Providence, RI, 2002. [.pdf]

 

Open problems in combinatorial group theory. Second edition (with G. Baumslag and

V. Shpilrain). Combinatorial and geometric group theory (New York, 2000/Hoboken, NJ,

 2001), 1-38, Contemp. Math., 296, Amer. Math. Soc., Providence, RI, 2002.

 

On the Andrews-Curtis equivalence (with A.D. Miasnikov and V. Shpilrain).

Combinatorial and geometric group theory (New York, 2000/Hoboken, NJ, 2001), 183-198.

Contemp. Math., 296, Amer. Math. Soc., Providence, RI, 2002. [.pdf]

We construct various examples of balanced presentations of the trivial group and show that some of them satisfy AC conjecture. We also consider AC-equivalence in metabelian groups and reveal some interesting connections of it with well-known problems in K-theory.

 

Stallings foldings and subgroups of free groups (with I. Kapovich). J. of Algebra, 248

 (2002), 608-668.

 

2001

 

Discriminating groups (with B. Fine, A.M. Gaglione and D. Spellman). J. of Group

Theory 4 (2001), no. 4, 463-474. [.pdf]

 

Implicit function theorem over free groups and genus problem (with O. Kharlampovich). Knots, braids, and mapping class groups---papers dedicated to Joan S. Birman (New York, 1998), 77-83, AMS/IP Stud. Adv. Math., 24, Amer. Math. Soc., Providence, RI, 2001. [.pdf]

 

Balanced presentations of the trivial group on two generators and the Andrews-Curtis

conjecture (with A.D. Miasnikov). Groups and computation, III (Columbus, OH, 1999),

257-263. Ohio State Univ. Math. Res. Inst. Publ. 8, de Gruyter, Berlin, 2001. [.pdf]

We proved that every balanced presentation on two generators of the trivial group satisfies

the AC conjecture.

 

2000

 

Discriminating and co-discriminating groups (with G. Baumslag and V. Remeslennikov). J.  Group Theory 3 (2000), no. 4, 467–479. [.pdf]

 

Algebraic geometry 2: logical foundations (with V. Remeslennikov). J. of Algebra 234

(2000),  225-276. [.pdf]

 

Centroids of groups (with S. Lioutikov). J. Group Theory, 3 (2000), no. 2, 177-197. [.pdf]

 

Algebraic geometry over groups (with G. Baumslag and V. Remeslennikov). Algorithmic

 problems in groups and semigroups (Lincoln, NE, 1998), 35-50, Trends Math., Birkhäuser  

 Boston, Boston, MA, 2000. [.pdf]

 

Aspects of the theory of free groups (with K. Bencsath, B. Fine, A. Gaglione, G.

Rosenberger and D. Spellman). Algorithmic problems in groups and semigroups (Lincoln,

NE, 1998), 35--50, Trends Math., Birkhäuser Boston, Boston, MA, 2000.

 

1999

 

Malnormality is decidable in free groups (with G.Baumslag and V.Remeslennikov).

Internat. Journal Algebra Comput. 9 (1999), no.6, 687-692. [.pdf]

 

Open problems in combinatorial group theory (with G. Baumslag and V. Shpilrain).

Groups, languages and geometry (South Hadley, MA, 1998), 1-27, Contemp. Math., 250,

Amer. Math. Soc., Providence, RI, 1999. [.pdf]

 

Equations over Q-completions of hyperbolic groups (with O. Kharlampovich and E.

Lyutikova). Trans. Amer. Math. Soc. 351 (1999), no. 7, 2961-2978.

 

Algebraic geometry over groups I. Algebraic sets and ideal theory (with G. Baumslag

and V. Remeslennikov). J. of Algebra 219 (1999), 16-79. [.pdf]

 

Description of fully residually free groups and irreducible affine varieties over a free

group (with O. Kharlampovich). Summer School in Group Theory in Banff, 1996, 71-80, 

CRM Proc. Lecture Notes, 17, Amer. Math. Soc., Providence, RI, 1999.

 

1998

 

A classification of  fully residually free groups of rank three or less (with A. Gaglione,

B. Fine, G. Rosenberger and D.Spellman). J. of Algebra, 200 (1998), no. 2, 571-605.

 

Irreducible affine varieties over a free group. II:  Systems in triangular quasi-quadratic

form and description of residually free groups (with O. Kharlampovich). J. of Algebra

200 (1998), no. 2, 517--570. [.pdf]

 

Irreducible affine varieties over a free group. I:  Irreducibility of quadratic equations

and Nullstellensatz (with O. Kharlampovich). J. of Algebra 200 (1998), no. 2, 472-516.

[.pdf]

 

Equations in free a Q-group (with O. Kharlampovich). Trans. Amer. Math. Soc. 350

(1998), no. 3, 947-974. [.pdf]

 

Hyperbolic groups and free constructions (with O. Kharlampovich). Trans. Amer. Math.

Soc. 350 (1998), no. 2, 571-613. [.pdf]

 

1997

 

Two theorems about equationally Noetherian groups (with G. Baumslag and V.

Romankov). J, of Algebra 194 (1997), 654-613. [.pdf]

 

Formal power series representations of free exponential groups (A.M. Gaglione, V.N.

Remeslennikov, D. Spellman). Comm. Algebra, 25 (1997), no. 2, 631-648.

 

1996

 

Exponential groups 2: extension of centralizers and tensor completion of CSA-groups

(with V. Remeslennikov). Internat. J. Algebra Comput. 6 (1996), no. 6, 687-711. [.pdf]

 

Length functions on free exponential groups (with V. Remeslennikov). Proc. IITPM SO

RAN 26, Omsk, 1996, 1-34.

 

1995 and earlier

 

Length functions on free exponential groups (with V. Remeslennikov). Proc.of Intern.

Conference in Analysis and Geometry, Omsk, 1995, 59-61.

 

CSA groups and separated free constructions (with D. Gildenhuys and O. Kharlampovich). Bull. Austr. Math. Soc. 52 (1995), no. 1, 63-84. [.pdf]

 

Logical languages and axioms for groups with a length function (with O. Kharlampovich and V. Remeslennikov). Proc. Inst. Appl. Math. Russian Acad. Sci. 20  (1995), 1-8.

 

Exponential groups I: foundations of the theory and tensor completions (with V.

Remeslennikov). Siberian Math. J.. 35 (1994), no. 5, 1106-1118.

 

Aproaches to the theory of computability (with I. Ashaev and V. Belyaev). Algebra i

Logika, 1994, v.4.

 

Recursively enumerable degrees over the reals (with V. Belyaev). Proc. of Intern. 

Algebraic Conf., Krasnoyarsk, 1993.

 

Model-theoretic problems of algebra. Dissertation, VINITI, Moscow, 1992.

 

Admissible sets in group theory (with V.Remeslennikov). Algebra i logika, 3 (1992).   

 

Weak second order logic in group theory (with V.Remeslennikov). Contemp. Math. 131

(1992), no. 2, 273-277.

 

Logic of finite types in group theory (with V.Remeslennikov). Bull. Siberian Math. Soc.,

Novosibirsk, 1990, 18-25.

 

Model theory of bilinear mappings. Siberian J. Math., 31 (1990), no. 3, 94-108.

 

Invariants of bilinear mappings. Siberian J. Math., 31 (1990), no. 1, 104-115.

 

Model-theoretical problems in group theory (with V.Remeslennikov). Problems of 

Algebra 4, Minsk, 1989.

 

Modules over local ring. Siberian J. Math., 30 (1989), no. 3, 72-83.

 

Structure of models and criteria of decidability of complete theories of finite-dimensional algebras (with V.Remeslennikov). Izvest. Akademii Nauk USSR, ser.math 53 (1989), no. 2., 379-397.

 

Recursive p-adic numbers and elementary theories of finitely generated pro-p-groups 

(with V.Remeslennikov). Izvest. Akademii Nauk USSR, ser.math 30 (1988), no.3.

 

Abstract isomorphisms and elementary theories of finite dimensional algebras and  

unipotent groups. Doklady Akademii Nauk USSR, 297 (1987), no. 2, 290-293.

 

Free operator groups with length function and finitely generated group of operators.

Computable invariants of algebraic structures., Novosibirsk, 1987, 87-97.

 

Elementary group equivalence with the integral length function (with V.Remeslennikov).

Illinois J. Math., 30 (1986), no. 2, 335-354.

 

Stable torsion-free rings and nilpotent groups. VII Soviet Union conf. on math. logic, 

Novosibirsk, 1984.

 

Generalized Nielsen transformations and trivial groups. Math. Notes, 5 (1984), no. 4, 491-

495.

 

Finite-dimensional algebras and k-groups of finite rank. Contemp. Math., 33 (1984), 436-

453.

 

Definability of Mal'cev bases and elementary properties of finite dimensional algebras. II   

(with V.Remeslennikov). Siberian J. Math., 24 (1982), no. 2, 97-113.

 

Definability of Mal'cev bases and elementary properties of finite dimensional algebras. I  

(with V.Remeslennikov). Siberian J. Math., 23 (1982), no. 5, 152-167.

 

Elementary properties of powered nilpotent groups (with V.Remeslennikov). Doklady

Akademii Nayuk 258 (1981), no. 5, 1056-1059.

 

Isomorphism and elementary properties of powered nilpotent groups (with 

V.Remeslennikov). Proc.Math.Institute  2, Nauka, Novosibirsk, 1981, 56-87.

 

On the approximability of groups of outer automorphisms of free groups of finite rank. 

 Algebra and Logic, 20 (1981), no.3, 291-299.