This Dagstuhl Seminar will be devoted to the study of algorithms in group theory as well as in commutative and tropical algebra, with the focus on complexity: worst-case, average-case, and generic-case.

Generic-case complexity. Generic-case, or just generic, complexity of algorithms was introduced by Kapovich, Myasnikov, Schupp, and Shpilrain in 2003. The original idea was to capture “practical” behavior of group-theoretic algorithms, as opposed to worst-case scenarios. Since then generic-case complexity found applications in logic, computer science, engineering and other areas. Still, probably the most well-developed applications of generic-case complexity to date are in the area of algorithmic group theory. In part this is due to the fact that the theory of random walks (which plays an important role in the theory) works particularly well in the context of groups.

Average-case complexity of algorithms was formally introduced by Levin in 1986 and informally considered before by Knuth in 1971. In the context of group theory, it was first discussed by Kapovich, Myasnikov, Schupp, and Shpilrain in 2005 although some ideas in the spirit of the average complexity in group theory were earlier put forward by Gromov. Specifically, Gromov in 1993 proposed to consider the averaged Dehn function instead of the usual Dehn function and suggested that the former might be asymptotically smaller than the latter.

An emerging direction in modern group theory is considering “classical" NP-hard problems from theoretical computer science (e.g. the subset sum problem and the knapsack problem) in the context of group theory to better understand how structural properties of groups correlate with their algorithmic complexity properties.

Commutative algebra. The main tool in computational commutative algebra is Buchberger's algorithm for computing Groebner bases. It is known to have a doubly exponential complexity in the number of indeterminates. However, this bound is rarely achieved and there are many classes of examples where the actual complexity is much lower. For polynomial systems having only finitely many solutions and for Boolean polynomial systems, it is known that the worst-case complexity of the Polynomial System Solving problem (PoSSo) and Boolean PoSSo is singly exponential in the number of indeterminates. In the last decades it has been an active area of research to find lower and upper complexity bounds for special types of polynomial systems.

Problems motivated by cryptography. Many interesting algorithmic problems in group theory were motivated by group-based cryptography that was popular in the beginning of the 21st century. Some of these problems are of great independent interest and will be discussed in this seminar. More recently, in 2014, the area of “tropical cryptography" was introduced by Grigoriev and Shpilrain. What it means is that min-plus algebras (a.k.a. tropical algebras) are used as platforms for various cryptographic primitives. That is, the usual operations of addition and multiplication are replaced by the operations min(x,y) and x+y, respectively. An obvious advantage of using tropical algebras as platforms is unparalleled efficiency because in tropical schemes, one does not have to perform any multiplications of numbers since tropical multiplication is the usual addition. Another useful (from the cryptographic point of view) feature is the presence of simply formulated problems that are easy in the “classical" case but become NP-hard in the tropical case. Examples include factoring a given tropical polynomial and factoring a given tropical matrix in a product of two matrices of given dimensions. However, the problem of factoring a tropical polynomial appears to be easy on a non-negligible set of inputs, which is not good for security. On the other hand, it appears likely that the problem of factoring a given tropical matrix may be hard generically. Proving rigorously that this problem is NP-hard generically (or on average) would be a spectacular and useful result.

Creative Commons BY 4.0

Bettina Eick, Alexander Hulpke, Martin Kreuzer, and Vladimir Shpilrain