Return to Revisions

4 of 8

added 47 characters in body; added 66 characters in body; added 7 characters in body

edited Dec 28, 2011 at 19:33

Moore determinant versus Vandermonde determinant complexity

This question is with regard to Elkies' answer to the above post.

What is the complexity of computing the determinant of a given $n \times n$ full rank Moore matrix modulo some integer?

Vandermonde determinant can be computed in $O(n\log^{a}{n})$ for some $a \in \mathbb{R}_{+}$.

Can Moore determinant be likewise reduced from $O(n^{3})$ to $O(n\log^{b}{n})$ for some $b \in \mathbb{R}_{+}$ (if so is there a reference)?

asked Dec 28, 2011 at 4:09