I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot find out where and how to apply Group Theory to other areas in CS, such as algorithms, data structres, graphs, complexity and so forth.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Here is one application to a counting problem. $\endgroup$– NotDijkstraJul 4, 2020 at 10:55
-
1$\begingroup$ This algorithm can be used to solve many puzzles, like Rubik's cube. $\endgroup$– NotDijkstraJul 4, 2020 at 10:57
-
4$\begingroup$ Coding theory often uses algebraic structures. $\endgroup$– Yuval FilmusJul 4, 2020 at 16:01
-
1$\begingroup$ I guess you could consider the Abel-Ruffini theorem to be an algorithmic lower bound result, as it asserts that some function cannot be computed using a particular model of computation. $\endgroup$– AreapersonJul 4, 2020 at 21:26
Add a comment
|
9 Answers
$\begingroup$
$\endgroup$
Algorithms for isomorphism problems such as graph isomorphism rely heavily on group theory.
An unusual example of group theory applied to computer science is the famous proof of Barrington's theorem, which uses the nonsolvability of the symmetric group $S_5$ to show equality of two complexity classes that superficially have nothing whatsoever to do with groups.
$\begingroup$
$\endgroup$
Group theory is indeed useful in algorithm design. For example, matrix multiplication is a fundamental problem for which such approaches have been used (see e.g., Cohn et al. [1] or these lecture notes).
There are also algebraic algorithms for other problems in e.g., graph theory (Hamiltonian path/cycle, graph motif, and various other path problems) based on techniques such as inclusion-exclusion and clever use of polynomials. These techniques often make use of finite field arithmetic.
$\begingroup$
$\endgroup$
The theory of continuous groups underlies a lot of modern computer graphics and computer vision, because Lie group theory is one of the more natural representations of a space of transformations.
Also, Galois theory is one of the workhorses of modern computer algebra systems.
$\begingroup$
$\endgroup$
Symmetry in combinatorial optimization.
An important group-theoretic algorithm often applied in theoretical computer science is Buchberger's algorithm.
$\begingroup$
$\endgroup$
1
Category Theory
If you accept Category Theory as a kind of generalization of groups, then we can conclude that modern type theory as related to the design of programming languages absolutely depends on it. For instance, take a look at this Q & A. Also, structures within programming languages, such as monads, are also categories.
-
9$\begingroup$ Yes, but seeing “Category Theory as a kind of generalization of groups” is a bit like seeing ‘Computer Science as a kind of generalisation of sorting algorithms’! $\endgroup$ Jul 5, 2020 at 15:30
$\begingroup$
$\endgroup$
Dijkstra shortest path algorithm relies heavily on algebraic properties of the way you compare/combine paths (we call it the algebra in this case). Network routing algorithms often use veresions of Dijkstra'a algorithm which are based on a different algebra, and their correctness is guaranteed by the algebraic properties of the compare/combine laws.
You can have a look at this document which describes in length how one can generalize Dijkstra's algorithm to other algebras than the usual $(\mathbb{R}, \min, +)$.
$\begingroup$
$\endgroup$
To give a yet another example, constraint satisfaction problems can be solved with a semiring formalism, using pretty much schoolbook algebra and lattices.
Also, any machine integers are a special case of a residue arithmetic, which is basically, $Z/nZ$. That's not mentioning all the computer algebra.
And formal "muscle" from undergrad algebra would help you with something like relational algebra (hello, SQL) or automata and formal languages, or communicating sequential processes and $\pi$-calculus (hello, theory of parallel computing).
$\begingroup$
$\endgroup$
1
There are many applications of group theory directly or indirectly to computer science. The group isomorphism problem in which given two groups to check if they are isomorphic or not. Let us assume that input groups are given by their multiplication tables. The fastest algorithm, in this case, is given by Tarjan (miller credited it to Tarjan)takes $n^{\log n}$ time. The idea is as follows, given $G$ and $H$, first find a generating set (say $S$) of $G$ (one can find it easily by the greedy algorithm) then set all possible maps from $S$ to $H$ (brute force) and check if any map is bijective homomorphism or not.
The group isomorphism problem when input groups are given by their Cayley table (multiplication table) polynomial-time reducible to the graph isomorphism problem. For graph isomorphism problem there has been lots of use of group theory. The graph isomorphism problem when input graphs have a degree at most three then also the algorithm used is heavily based on group theory.
There has been work on data structures and algorithm side also when input groups are given by a set of generators. Even there has been a data structure (like Schreier–Sims tree or vectors) that is designed for a group theory. See Link
There are many other interesting problems that have been studied in the past like finding the minimum generating set of a group given by a Cayley table. Arvind and Toran design a polynomial-time algorithm for nilpotent groups (groups very close to commutative groups). See link.
One more interesting problem is given a group and you need to compute all indecomposable factors. If you don't know much about group theory then think like you are given a number and want to factor it into prime factor. There are polynomial-time algorithms for this problem whether the input group is given by generating set or Cayley table.
Groups when given by generator relator representation, in this case, many problems like chacking whether a given group is nontrivial or finite are undecidable.
-
2$\begingroup$ This answer mostly seems to describe applications of computer science to group theory, rather than applications of group theory to computer science. $\endgroup$ Jul 5, 2020 at 17:39
$\begingroup$
$\endgroup$
Group theory is also useful, via applications to number theory, in non-cryptographic pseudorandom number generating algorithms. See for example Niederreiter and Winterhof's Applied Number Theory (which also discusses cryptography and other CS topics).
The chapter on PRNGs in that book focuses mainly on simple algorithms such as linear congruent generators, but I'm pretty sure that group theory also plays a role in recent more complex PRNGs such as generalized linear shift registers. Those definitely make use of finite fields, but I'm not sure to what extent results from group theory per se are important for those algorithms.
