# On Determinant modulo $2^k$ complexity

Determinant of integer matrix modulo $$2$$ is complete for the class $$\oplus L$$. Is determinant modulo $$2^k$$ computable in $$\oplus L$$ at any fixed $$k$$?

How about if $$k=o(n)$$ where matrix is $$n\times n$$?

• Have you looked at Valiant's algorithm? – Joshua Grochow Feb 18 at 5:15
• Actually I think it provides $n^{O(k)}$ algorithm but no I am not familiar in the workings of it. – 1.. Feb 18 at 5:16
• Theorem 1 in newtraell.cs.uchicago.edu/files/phd_paper/raghav.pdf provides $\oplus L$-completeness for $k=O(1)$. – 1.. Feb 18 at 5:40
• Nice find - I can't believe I forgot about that result, now that I see it I recall him telling me about it in person! It'd be worth updating the question. Also, to your second part about growing k, why this question? Would you be interested in fixed-parameter complexity? – Joshua Grochow Feb 18 at 14:43
• How $\oplus L$ interpolates to $\mathsf{NC}^2$ and how it deviates from $PP$ as $k=\Omega(n)$? – 1.. Feb 18 at 14:59