Black box group

Last updated

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:

Contents

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. [1] 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, [2] the Product Replacement Algorithm, [3] and testing group commutativity . [4]

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. [5]

See also

Notes

  1. ↑ Babai, L.; Szemeredi, E. (1984). "On the Complexity of Matrix Group Problems I". 25th Annual Symposium on Foundations of Computer Science, 1984. pp. 229–240. doi:10.1109/SFCS.1984.715919. ISBN   0-8186-0591-X.
  2. ↑ L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proc. 23rd STOC (1991), 164–174.
  3. ↑ Frank Celler; Charles R. Leedham-Green; Scott H. Murray; Alice C. Niemeyer; E.A. O'Brien (1995). "Generating random elements of a finite group". Communications in Algebra. 23 (3): 4931–4948. CiteSeerX   10.1.1.43.2250 . doi:10.1080/00927879508825509.
  4. ↑ Pak, Igor (2012). "Testing commutativity of a group and the power of randomization". LMS Journal of Computation and Mathematics. 15: 38–43. doi: 10.1112/S1461157012000046 .
  5. ↑ See Hоlt et al. (2005).

Related Research Articles

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

In cryptography, a random oracle is an oracle that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time that query is submitted.

<span class="mw-page-title-main">Spanning tree</span> Tree which includes all vertices of a graph

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

In mathematics, computational group theory is the study of groups by means of computers. It is concerned with designing and analysing algorithms and data structures to compute information about groups. The subject has attracted interest because for many interesting groups (including most of the sporadic groups) it is impractical to perform calculations by hand.

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

<span class="mw-page-title-main">László Babai</span> Hungarian mathematician and computer scientist

László "Laci" Babai is a Hungarian professor of computer science and mathematics at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields.

In mathematics, especially the field of computational group theory, a Schreier vector is a tool for reducing the time and space complexity required to calculate orbits of a permutation group.

Let be a finite permutation group acting on a set . A sequence

<span class="mw-page-title-main">Charles Leedham-Green</span> British mathematician

Charles R. Leedham-Green is a retired professor of mathematics at Queen Mary, University of London, known for his work in group theory. He completed his DPhil at the University of Oxford.

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, Nielsen transformations, named after Jakob Nielsen, are certain automorphisms of a free group which are a non-commutative analogue of row reduction and one of the main tools used in studying free groups,. They were introduced in to prove that every subgroup of a free group is free, but are now used in a variety of mathematics, including computational group theory, k-theory, and knot theory. The textbook devotes all of chapter 3 to Nielsen transformations.

In graph theory, a branch of mathematics, graph canonization is the problem of finding a canonical form of a given graph G. A canonical form is a labeled graph Canon(G) that is isomorphic to G, such that every graph that is isomorphic to G has the same canonical form as G. Thus, from a solution to the graph canonization problem, one could also solve the problem of graph isomorphism: to test whether two graphs G and H are isomorphic, compute their canonical forms Canon(G) and Canon(H), and test whether these two canonical forms are identical.

<span class="mw-page-title-main">Inversion (discrete mathematics)</span> Pair of positions in a sequence where two elements are out of sorted order

In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order.

In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or the spanning trees of a graph, among other applications.

Anna Lubiw is a computer scientist known for her work in computational geometry and graph theory. She is currently a professor at the University of Waterloo.

In mathematics, more specifically in computational algebra, a straight-line program (SLP) for a finite group G = ⟨S⟩ is a finite sequence L of elements of G such that every element of L either belongs to S, is the inverse of a preceding element, or the product of two preceding elements. An SLP L is said to compute a group element g ∈ G if g ∈ L, where g is encoded by a word in S and its inverses.

In the area of abstract algebra known as group theory, the diameter of a finite group is a measure of its complexity.

Birkhoff's algorithm is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.