Neeraj Kayal, Timur Nezhmetdinov

We give a polynomial time algorithm that computes a

decomposition of a finite group G given in the form of its

multiplication table. That is, given G, the algorithm outputs two

subgroups A and B of G such that G is the direct product

of A ...
more >>>

Joshua Grochow, Youming Qiao

The isomorphism problem for groups given by multiplication tables (GpI) is well-known to be solvable in n^O(log n) time, but only recently has there been significant progress towards polynomial time. For example, in 2012 Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. ... more >>>

Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe

We show an O(sqrt(n))-space and polynomial-time algorithm for solving the planar directed graph reachability problem. Imai et al. showed in CCC 2013 that the problem is solvable in O(n^{1/2+eps})-space and polynomial-time by using separators for planar graphs, and it has been open whether the space bound can be improved to ... more >>>