Skip to content

Research at St Andrews

Constructive membership in black-box groups

Research output: Contribution to journalArticlepeer-review

DOI

Author(s)

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

School/Research organisations

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.

Close

Details

Original languageEnglish
Pages (from-to)747-763
Number of pages17
JournalJournal of Group Theory
Volume11
Issue number6
Early online date30 Sep 2008
DOIs
Publication statusPublished - Nov 2008

    Research areas

  • LIE TYPE, RECOGNITION, PROBABILITY, ALGORITHM, ELEMENT

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

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