|
Black Box Group
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'', ≤ 2''N'' shows that ''G'' is finite. Applications The black box groups were introduced by Babai and Szemerédi in 1984. 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, the ''Product Replacement Algorithm'', and '' testing group commutativity''. Many early algorithms in CGT, such as the Schreier–Sims algorithm ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Group Theory
In mathematics, computational group theory is the study of group (mathematics), 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. Important algorithms in computational group theory include: * the Schreier–Sims algorithm for finding the order (group theory), order of a permutation group * the Todd–Coxeter algorithm and Knuth–Bendix algorithm for coset enumeration * the product-replacement algorithm for finding random elements of a group Two important computer algebra systems (CAS) used for group theory are GAP computer algebra system, GAP and Magma computer algebra system, Magma. Historically, other systems such as CAS (for character theory) and Cayley computer algebra system, Cayley (a predecessor of Magma) were important. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Property Testing
Property testing is a field of theoretical computer science, concerned with the design of super-fast algorithms for approximate decision making, where the decision refers to properties or parameters of huge objects. A ''property testing algorithm'' for a decision problem is an algorithm whose query complexity (the number of queries made to its input) is much smaller than the instance size of the problem. Typically, property testing algorithms are used to determine whether some combinatorial structure (such as a graph or a boolean function) satisfies some property , or is "far" from having this property (meaning that an -fraction of the representation of must be modified to make satisfy ), using only a small number of "local" queries to the object. For example, the following promise problem admits an algorithm whose query complexity is independent of the instance size (for an arbitrary constant ): :"Given a graph on vertices, decide whether it is bipartite, or cannot be ma ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
American Mathematical Society
The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, advocacy and other programs. The society is one of the four parts of the Joint Policy Board for Mathematics and a member of the Conference Board of the Mathematical Sciences. History The AMS was founded in 1888 as the New York Mathematical Society, the brainchild of Thomas Fiske, who was impressed by the London Mathematical Society on a visit to England. John Howard Van Amringe became the first president while Fiske became secretary. The society soon decided to publish a journal, but ran into some resistance over concerns about competing with the '' American Journal of Mathematics''. The result was the ''Bulletin of the American Mathematical Society'', with Fiske as editor-in-chief. The de facto journal, as intended, was influentia ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Matroid Oracle
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. The most commonly used oracle of this type is an independence oracle, a subroutine for testing whether a set of matroid elements is independent. Several other types of oracle have also been used; some of them have been shown to be weaker than independence oracles, some stronger, and some equivalent in computational power.; ; . Many algorithms that perform computations on matroids have been designed to take an oracle as input, allowing them to run efficiently without change on many different kinds of matroids, and without additional assumptions about what kind of matroid they are using. For instance, given an independence oracle for any matroid, it is possible to find the minimum weigh ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Implicit Graph
In the study of graph algorithms, an implicit graph representation (or more simply implicit graph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from some other input, for example a computable function. Neighborhood representations The notion of an implicit graph is common in various search algorithms which are described in terms of graphs. In this context, an implicit graph may be defined as a set of rules to define all Neighborhood (graph theory), neighbors for any specified vertex. This type of implicit graph representation is analogous to an adjacency list, in that it provides easy access to the neighbors of each vertex. For instance, in searching for a solution to a puzzle such as Rubik's Cube, one may define an implicit graph in which each vertex represents one of the possible states of the cube, and each edge represents a move ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Charles Leedham-Green
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. His parents were John Charles Leedham-Green (1902–1984), a surgeon and general practitioner in Southwold, and Gertrude Mary Somerville Caldwell. Work With Leonard Soicher, Leedham-Green designed the product replacement algorithm; an algorithm within computational group theory that generates random elements of groups by taking a random walk through the group. This algorithm has been implemented in both GAP and MAGMA. He is responsible for a great body of work in group theory. In recent times, this has involved research in computational group theory and pro-p groups. The 300th edition of the ''Journal of Algebra'' was dedicated to him for his 65th birthday. On the occasion of his retirement in 2006, the Mathematics Research Centre at Queen Mary held a conference in celebration of his mathem ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Group Representation
In the mathematical field of representation theory, group representations describe abstract groups in terms of bijective linear transformations of a vector space to itself (i.e. vector space automorphisms); in particular, they can be used to represent group elements as invertible matrices so that the group operation can be represented by matrix multiplication. In chemistry, a group representation can relate mathematical group elements to symmetric rotations and reflections of molecules. Representations of groups allow many group-theoretic problems to be reduced to problems in linear algebra. In physics, they describe how the symmetry group of a physical system affects the solutions of equations describing that system. The term ''representation of a group'' is also used in a more general sense to mean any "description" of a group as a group of transformations of some mathematical object. More formally, a "representation" means a homomorphism from the group to the autom ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Schreier–Sims Algorithm
The Schreier–Sims algorithm is an algorithm in computational group theory, named after the mathematicians Otto Schreier and Charles Sims. This algorithm can find the order of a finite permutation group, determine whether a given permutation is a member of the group, and other tasks in polynomial time. It was introduced by Sims in 1970, based on Schreier's subgroup lemma. The running time was subsequently improved by Donald Knuth in 1991. Later, an even faster randomized version of the algorithm was developed. Background and timing The algorithm is an efficient method of computing a base and strong generating set (BSGS) of a permutation group. In particular, an SGS determines the order of a group and makes it easy to test membership in the group. Since the SGS is critical for many algorithms in computational group theory, computer algebra systems typically rely on the Schreier–Sims algorithm for efficient calculations in groups. The running time of Schrei ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quantum Algorithm
In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) 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 generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement. Problems that are undecidable using classical computers remain undecidable using quantum computers. What makes quantum algorithms interesting is that they might be able to solve some problems fa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Endre Szemerédi
Endre Szemerédi (; born August 21, 1940) is a Hungarian-American mathematician and computer scientist, working in the field of combinatorics and theoretical computer science. He has been the State of New Jersey Professor of computer science at Rutgers University since 1986. He also holds a professor emeritus status at the Alfréd Rényi Institute of Mathematics of the Hungarian Academy of Sciences. Szemerédi has won prizes in mathematics and science, including the Abel Prize in 2012. He has made a number of discoveries in combinatorics and computer science, including Szemerédi's theorem, the Szemerédi regularity lemma, the Erdős–Szemerédi theorem, the Hajnal–Szemerédi theorem and the Szemerédi–Trotter theorem. Early life Szemerédi was born in Budapest. Since his parents wished him to become a doctor, Szemerédi enrolled at a college of medicine, but he dropped out after six months (in an interview he explained it: "I was not sure I could do work bearing su ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Group (mathematics)
In mathematics, a group is a Set (mathematics), set with an Binary operation, operation that combines any two elements of the set to produce a third element within the same set and the following conditions must hold: the operation is Associative property, associative, it has an identity element, and every element of the set has an inverse element. For example, the integers with the addition, addition operation form a group. The concept of a group was elaborated for handling, in a unified way, many mathematical structures such as numbers, geometric shapes and polynomial roots. Because the concept of groups is ubiquitous in numerous areas both within and outside mathematics, some authors consider it as a central organizing principle of contemporary mathematics. In geometry, groups arise naturally in the study of symmetries and geometric transformations: The symmetries of an object form a group, called the symmetry group of the object, and the transformations of a given type form a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
László Babai
László "Laci" Babai (born July 20, 1950, in Budapest) a fellow of the American Academy of Arts and Sciences, and won the Knuth Prize. Babai was an invited speaker at the International Congresses of Mathematicians in Kyoto (1990), Zürich (1994, plenary talk), and Rio de Janeiro Rio de Janeiro, or simply Rio, is the capital of the Rio de Janeiro (state), state of Rio de Janeiro. It is the List of cities in Brazil by population, second-most-populous city in Brazil (after São Paulo) and the Largest cities in the America ... (2018). Sources Professor László Babai's algorithm is next big step in conquering isomorphism in graphs// Published on Nov 20, 2015 Division of the Physical Sciences / The University of Chicago Mathematician claims breakthrough in complexity theory by Adrian Cho 10 November 2015 17:45 // Posted iMath Science AAAS News A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details+ Background on Graph Isomorphism + The Main Result // Math ∩ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
