Algorithmic theory of free solvable groups: Randomized computations

Alexander Ushakov

doi:10.1016/j.jalgebra.2014.02.014

Algorithmic theory of free solvable groups: Randomized computations

Alexander Ushakov

Department of Mathematical Sciences

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

We design new deterministic and randomized algorithms for computational problems in free solvable groups. In particular, we prove that the word problem and the power problem can be solved in quasi-linear time and the conjugacy problem can be solved in quasi-quartic time by Monte Carlo type algorithms.

Original language	English
Pages (from-to)	178-200
Number of pages	23
Journal	Journal of Algebra
Volume	407
DOIs	https://doi.org/10.1016/j.jalgebra.2014.02.014
State	Published - 1 Jun 2014

Keywords

Conjugacy problem
Cyclic subgroup membership
Metabelian groups
Power problem
Randomized algorithms
Solvable groups
Word problem

Access to Document

10.1016/j.jalgebra.2014.02.014

Cite this

@article{0c0661063529478ab152b29ba3305800,

title = "Algorithmic theory of free solvable groups: Randomized computations",

abstract = "We design new deterministic and randomized algorithms for computational problems in free solvable groups. In particular, we prove that the word problem and the power problem can be solved in quasi-linear time and the conjugacy problem can be solved in quasi-quartic time by Monte Carlo type algorithms.",

keywords = "Conjugacy problem, Cyclic subgroup membership, Metabelian groups, Power problem, Randomized algorithms, Solvable groups, Word problem",

author = "Alexander Ushakov",

year = "2014",

month = jun,

day = "1",

doi = "10.1016/j.jalgebra.2014.02.014",

language = "English",

volume = "407",

pages = "178--200",

}

TY - JOUR

T1 - Algorithmic theory of free solvable groups

T2 - Randomized computations

AU - Ushakov, Alexander

PY - 2014/6/1

Y1 - 2014/6/1

N2 - We design new deterministic and randomized algorithms for computational problems in free solvable groups. In particular, we prove that the word problem and the power problem can be solved in quasi-linear time and the conjugacy problem can be solved in quasi-quartic time by Monte Carlo type algorithms.

AB - We design new deterministic and randomized algorithms for computational problems in free solvable groups. In particular, we prove that the word problem and the power problem can be solved in quasi-linear time and the conjugacy problem can be solved in quasi-quartic time by Monte Carlo type algorithms.

KW - Conjugacy problem

KW - Cyclic subgroup membership

KW - Metabelian groups

KW - Power problem

KW - Randomized algorithms

KW - Solvable groups

KW - Word problem

UR - https://www.scopus.com/pages/publications/84897415856

UR - https://www.scopus.com/pages/publications/84897415856#tab=citedBy

U2 - 10.1016/j.jalgebra.2014.02.014

DO - 10.1016/j.jalgebra.2014.02.014

M3 - Article

AN - SCOPUS:84897415856

SN - 0021-8693

VL - 407

SP - 178

EP - 200

JO - Journal of Algebra

JF - Journal of Algebra

ER -

Algorithmic theory of free solvable groups: Randomized computations

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this