Title: Linear algebraic analogues of the graph isomorphism problem and the Erdős-Rényi model,
Abstract: A classical difficult isomorphism testing problem is to test isomorphism of
p-groups of class 2 and exponent p in time polynomial in the group order. It is
known that this problem can be reduced to solving the alternating matrix space
isometry problem over a finite field in time polynomial in the underlying
vector space size. We propose a venue of attack for the latter problem by
viewing it as a linear algebraic analogue of the graph isomorphism problem.
This viewpoint leads us to explore the possibility of transferring techniques
for graph isomorphism to this long-believed bottleneck case of group
isomorphism.
In 1970's, Babai, Erdős, and Selkow presented the first average-case
efficient graph isomorphism testing algorithm (SIAM J Computing, 1980).
Inspired by that algorithm, we devise an average-case efficient algorithm for
the alternating matrix space isometry problem over a key range of parameters,
in a random model of alternating matrix spaces in vein of the Erdős-Rényi
model of random graphs. For this, we develop a linear algebraic analogue of the
classical individualisation technique, a technique belonging to a set of
combinatorial techniques that has been critical for the progress on the
worst-case time complexity for graph isomorphism, but was missing in the group
isomorphism context. As a consequence of the main algorithm, we establish a
weaker linear algebraic analogue of Erdős and Rényi's classical result
that most graphs have the trivial automorphism group. We finally show that
Luks' dynamic programming technique for graph isomorphism (STOC 1999) can be
adapted to slightly improve the worst-case time complexity of the alternating
matrix space isometry problem in a certain range of parameters.