# Tag Info

18

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

13

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

8

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.

6

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

5

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.

3

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

3

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

2

How about: Build a weighted complete bipartite graph where the left vertex set is $S$, the right vertex set is $G$, and the weight of the edge between $s \in S$ and $g \in G$ is the 3-D Manhattan distance from $s$ to $g$. Solve the assignment problem for this graph. This finds the exact minimum. It does unfortunately take about $O(n^3)$ for a typical ...

1

Suppose that we had a stronger guarantee: $A'$ is a randomized algorithm, and for every $b$, $\Pr[A'(b) = \log_g b] > 1/2$, over the randomness of the algorithm. In that case, you would construct $A$ by running $A'$ several times, and checking each output until you get one that satisfies $g^{A'(b)} = b$. Now suppose that the guarantee is $\Pr_b[A'(b) = \... 1 This problem, that I will call Subset-Perm-Sum, is NP-complete. Membership is easy: guess the subset non-deterministically and then check. For hardness one can reduce from 3CNF-SAT in a very similar way to the standard proof of hardness for Subset-Sum. Let$\varphi$be an input formula with$v$variables and$c\$ clauses. We will build an instance of Subset-...

Only top voted, non community-wiki answers of a minimum length are eligible