Black box group
{{Group theory sidebar}}
In computational group theory, a black box group (black-box group) is a group G whose elements are encoded by bit strings of length N, and group operations are performed by an oracle (the "black box"). These operations include:
- taking a product g·h of elements g and h,
- taking an inverse g−1 of element g,
- deciding whether g = 1.
This class is defined to include both the permutation groups and the matrix groups. The upper bound on the order of G given by |G| ≤ 2N shows that G is finite.
Applications
The black box groups were introduced by Babai and Szemerédi in 1984.{{Cite book|last1=Babai|first1=L.|last2=Szemeredi|first2=E.|title=25th Annual Symposium on Foundations of Computer Science, 1984 |chapter=On the Complexity of Matrix Group Problems I |year=1984|pages=229–240|doi=10.1109/SFCS.1984.715919|isbn=0-8186-0591-X}} They were used as a formalism for (constructive) group recognition and property testing. Notable algorithms include the Babai's algorithm for finding random group elements,L. Babai, [http://dl.acm.org/citation.cfm?id=103440 Local expansion of vertex-transitive graphs and random generation in finite groups], Proc. 23rd STOC (1991), 164–174. the Product Replacement Algorithm,{{cite journal
|author1=Frank Celler |author2=Charles R. Leedham-Green |author3=Scott H. Murray |author4=Alice C. Niemeyer |author5=E.A. O'Brien |year=1995
|title=Generating random elements of a finite group
|journal= Communications in Algebra
|volume=23 |issue=3 |pages=4931–4948
|doi=10.1080/00927879508825509
|citeseerx=10.1.1.43.2250 }}
and testing group commutativity.
{{cite journal
|last=Pak |first=Igor |author1-link=Igor Pak
|year=2012
|title=Testing commutativity of a group and the power of randomization
|journal= LMS Journal of Computation and Mathematics
|volume=15 |pages=38–43
|doi=10.1112/S1461157012000046
|doi-access=free
}}
Many early algorithms in CGT, such as the Schreier–Sims algorithm, require a permutation representation of a group and thus are not black box. Many other algorithms require finding element orders. Since there are efficient ways of finding the order of an element in a permutation group or in a matrix group (a method for the latter is described by Celler and Leedham-Green in 1997), a common recourse is to assume that the black box group is equipped with a further oracle for determining element orders.See Holt et al. (2005).
See also
Notes
References
- Derek F. Holt, Bettina Eick, Eamonn A. O'Brien, Handbook of computational group theory, Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, Florida, 2005. {{ISBN|1-58488-372-3}}
- Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. {{ISBN|0-521-66103-X}}.
- {{cite book |authorlink1=William Kantor | title=Black Box Classical Groups | series=Memoirs of the American Mathematical Society | issn=0065-9266 | volume=708 | first1=William M. | last1=Kantor | first2=Ákos | last2=Seress | publisher=American Mathematical Society | year=2001 | isbn=978-0-8218-2619-5 }}