Skip to content

Research at St Andrews

Constructive membership in black-box groups

Research output: Contribution to journalArticlepeer-review

DOI

Standard

Constructive membership in black-box groups. / Holmes, Petra Elisabeth; Linton, Stephen Alexander; O'Brien, E. A.; Ryba, A. J. E.; Wilson, R. A.

In: Journal of Group Theory, Vol. 11, No. 6, 11.2008, p. 747-763.

Research output: Contribution to journalArticlepeer-review

Harvard

Holmes, PE, Linton, SA, O'Brien, EA, Ryba, AJE & Wilson, RA 2008, 'Constructive membership in black-box groups', Journal of Group Theory, vol. 11, no. 6, pp. 747-763. https://doi.org/10.1515/JGT.2008.047

APA

Holmes, P. E., Linton, S. A., O'Brien, E. A., Ryba, A. J. E., & Wilson, R. A. (2008). Constructive membership in black-box groups. Journal of Group Theory, 11(6), 747-763. https://doi.org/10.1515/JGT.2008.047

Vancouver

Holmes PE, Linton SA, O'Brien EA, Ryba AJE, Wilson RA. Constructive membership in black-box groups. Journal of Group Theory. 2008 Nov;11(6):747-763. https://doi.org/10.1515/JGT.2008.047

Author

Holmes, Petra Elisabeth ; Linton, Stephen Alexander ; O'Brien, E. A. ; Ryba, A. J. E. ; Wilson, R. A. / Constructive membership in black-box groups. In: Journal of Group Theory. 2008 ; Vol. 11, No. 6. pp. 747-763.

Bibtex - Download

@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",

}

RIS (suitable for import to EndNote) - Download

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

VL - 11

SP - 747

EP - 763

JO - Journal of Group Theory

JF - Journal of Group Theory

SN - 1433-5883

IS - 6

ER -

Related by author

  1. Polynomial-time proofs that groups are hyperbolic

    Holt, D., Linton, S., Neunhoeffer, M., Parker, R., Pfeiffer, M. & Roney-Dougal, C. M., May 2021, In: Journal of Symbolic Computation. 104, p. 419-475

    Research output: Contribution to journalArticlepeer-review

  2. GAP – Groups, Algorithms, and Programming, Version 4.11.1

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 2 Mar 2021

    Research output: Non-textual formSoftware

  3. GAP – Groups, Algorithms, and Programming, Version 4.11.0

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 29 Feb 2020

    Research output: Non-textual formSoftware

  4. GAP – Groups, Algorithms, and Programming, Version 4.10.2

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 19 Jun 2019

    Research output: Non-textual formSoftware

  5. GAP – Groups, Algorithms, and Programming, Version 4.10.1

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 23 Feb 2019

    Research output: Non-textual formSoftware

Related by journal

  1. Approximation of automorphisms of the rationals and the random graph

    Darji, U. & Mitchell, J. D., 2011, In: Journal of Group Theory. 14, 3, p. 361-388 28 p.

    Research output: Contribution to journalArticlepeer-review

  2. The power graph of a finite group, II

    Cameron, P. J., 2010, In: Journal of Group Theory. 13, p. 779-783

    Research output: Contribution to journalArticlepeer-review

  3. Certain classical groups are not well-defined

    Roney-Dougal, C. M., Bray, J. & Holt, D., 2009, In: Journal of Group Theory. 12, p. 171-180

    Research output: Contribution to journalArticlepeer-review

  4. On the single-orbit conjecture for uncoverings-by-bases

    Bailey, R. F. & Cameron, P. J., 2008, In: Journal of Group Theory. 11, p. 845-850

    Research output: Contribution to journalArticlepeer-review

ID: 597840

Top