|
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 al ... [...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. S ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Property Testing
In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to distinguish if some combinatorial structure ''S'' (such as a graph or a boolean function) satisfies some property ''P'', or is "far" from having this property (meaning an ε-fraction of the representation of ''S'' need be modified in order to make ''S'' satisfy ''P''), 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 ε > 0): :"Given a graph ''G'' on ''n'' vertices, decide if ''G'' is bipartite, or ''G'' cannot be made bipartite even after removing an arbitrary subset of at most \epsilon\tbinom n2 edges of ''G''." Property testing algorithms are central to the definition of probabilistically ch ... [...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 was the first president and Fiske became secretary. The society soon decided to publish a journal, but ran into some resistance, due to 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 influential in in ... [...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 whose 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 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 from one state to another. It is straightforward to generate the neighbors of any ... [...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 ''Journal of Algebra'' (ISSN 0021-8693) is an international mathematical research journal in algebra. An imprint of Academic Press, it is published by Elsevier. ''Journal of Algeb ... [...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 are important because they allow many group-theoretic problems to be reduced to problems in linear algebra, which is well understood. They are also important in physics because, for example, 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 o ... [...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, test membership (is a given permutation contained in a group?), and many other tasks in polynomial time. It was introduced by Sims in 1970, based on Schreier's subgroup lemma. The timing 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 Schreier–Sims va ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quantum Algorithm
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 (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 usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement. Problems which 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 such r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Group (mathematics)
In mathematics, a group is a Set (mathematics), set and an Binary operation, operation that combines any two Element (mathematics), elements of the set to produce a third element of the set, in such a way that the operation is Associative property, associative, an identity element exists and every element has an Inverse element, inverse. These three axioms hold for Number#Main classification, number systems and many other mathematical structures. For example, the integers together with the addition operation form a group. The concept of a group and the axioms that define it were elaborated for handling, in a unified way, essential structural properties of very different mathematical entities 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 ... [...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 ( , , ; literally 'River of January'), or simply Rio, is the capital of the state of the same name, Brazil's third-most populous state, and the second-most populous city in Brazil, after São Paulo. Listed by the GaWC as a b ... (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 ∩ P ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
