Constructive membership in black-box groups

Petra Elisabeth Holmes; Stephen Alexander Linton; E. A. O'Brien; A. J. E. Ryba; R. A. Wilson

doi:10.1515/JGT.2008.047

Constructive membership in black-box groups

Petra Elisabeth Holmes, Stephen Alexander Linton, E. A. O'Brien, A. J. E. Ryba, R. A. Wilson

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

Abstract

We present an algorithm to reduce the constructive membership problem for a black-box group G to three instances of the same problem for involution centralizers in G. If G is a finite simple group of Lie type in odd characteristic, then this reduction can be performed in (Monte Carlo) polynomial time.

Original language	English
Pages (from-to)	747-763
Number of pages	17
Journal	Journal of Group Theory
Volume	11
Issue number	6
Early online date	30 Sept 2008
DOIs	https://doi.org/10.1515/JGT.2008.047
Publication status	Published - Nov 2008

Keywords

LIE TYPE
RECOGNITION
PROBABILITY
ALGORITHM
ELEMENT

Access to Document

10.1515/JGT.2008.047

Cite this

@article{71d7810089e94a9bb2f8592739a76895,

title = "Constructive membership in black-box groups",

abstract = "We present an algorithm to reduce the constructive membership problem for a black-box group G to three instances of the same problem for involution centralizers in G. If G is a finite simple group of Lie type in odd characteristic, then this reduction can be performed in (Monte Carlo) polynomial time.",

keywords = "LIE TYPE, RECOGNITION, PROBABILITY, ALGORITHM, ELEMENT",

author = "Holmes, {Petra Elisabeth} and Linton, {Stephen Alexander} and O'Brien, {E. A.} and Ryba, {A. J. E.} and Wilson, {R. A.}",

year = "2008",

month = nov,

doi = "10.1515/JGT.2008.047",

language = "English",

volume = "11",

pages = "747--763",

journal = "Journal of Group Theory",

issn = "1433-5883",

publisher = "de Gruyter",

number = "6",

}

TY - JOUR

T1 - Constructive membership in black-box groups

AU - Holmes, Petra Elisabeth

AU - Linton, Stephen Alexander

AU - O'Brien, E. A.

AU - Ryba, A. J. E.

AU - Wilson, R. A.

PY - 2008/11

Y1 - 2008/11

N2 - We present an algorithm to reduce the constructive membership problem for a black-box group G to three instances of the same problem for involution centralizers in G. If G is a finite simple group of Lie type in odd characteristic, then this reduction can be performed in (Monte Carlo) polynomial time.

AB - We present an algorithm to reduce the constructive membership problem for a black-box group G to three instances of the same problem for involution centralizers in G. If G is a finite simple group of Lie type in odd characteristic, then this reduction can be performed in (Monte Carlo) polynomial time.

KW - LIE TYPE

KW - RECOGNITION

KW - PROBABILITY

KW - ALGORITHM

KW - ELEMENT

UR - http://www.scopus.com/inward/record.url?scp=53349109538&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1515/JGT.2008.047

U2 - 10.1515/JGT.2008.047

DO - 10.1515/JGT.2008.047

M3 - Article

SN - 1433-5883

VL - 11

SP - 747

EP - 763

JO - Journal of Group Theory

JF - Journal of Group Theory

IS - 6

ER -

Constructive membership in black-box groups

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications

Cite this

Constructive membership in black-box groups

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications

Cite this