19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Here is one application to a counting problem. $\endgroup$ – NotDijkstra Jul 4 at 10:55
  • 1
    $\begingroup$ This algorithm can be used to solve many puzzles, like Rubik's cube. $\endgroup$ – NotDijkstra Jul 4 at 10:57
  • 4
    $\begingroup$ Coding theory often uses algebraic structures. $\endgroup$ – Yuval Filmus Jul 4 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$ – Lorenzo Najt Jul 4 at 21:26
17
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
12
$\begingroup$

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.


[1] Cohn, H., Kleinberg, R., Szegedy, B. and Umans, C., 2005, October. Group-theoretic algorithms for matrix multiplication. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) (pp. 379-388). IEEE.

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 8
    $\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$ – leftaroundabout Jul 5 at 15:30
5
$\begingroup$

Symmetry in combinatorial optimization.

An important group-theoretic algorithm often applied in theoretical computer science is Buchberger's algorithm.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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, +)$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 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$ – Aaron Rotenberg Jul 5 at 17:39
2
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.