3 ms·
I believe this is the punchline but I still can't figure out what the 6 is about: To obtain Theorem 1.1, let k denote logp(n). We apply Theorem 1.2 for the
by hinkley 3y ago
I believe this is the punchline but I still can't figure out what the 6 is about:
To obtain Theorem 1.1, let k denote logp(n). We apply Theorem 1.2 for the case of k > (log2(p))^5
by constructing the skew-symmetric matrix spaces for both input groups according to the Baer’s
correspondence [Bae38]. Theorem 1.2 implies the running time for this case is n^O((log n)5/6). For the
case of k ≤ (log2(p))^5 , we run the aforementioned generating set enumeration algorithm [Mil78].
Because every p group of order p^k has a generating set of size at most k, the running time of the
algorithm for this case is p^O(k2), which is also n^O((log n)5/6).
pasting dropped some superscripts to regular scripts. I tried to fix them but I may have borked a couple.