0
$\begingroup$

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$?

$\endgroup$
5
  • $\begingroup$ Have you looked at Valiant's algorithm? $\endgroup$ Feb 18 at 5:15
  • $\begingroup$ Actually I think it provides $n^{O(k)}$ algorithm but no I am not familiar in the workings of it. $\endgroup$
    – Mr.
    Feb 18 at 5:16
  • 1
    $\begingroup$ Theorem 1 in newtraell.cs.uchicago.edu/files/phd_paper/raghav.pdf provides $\oplus L$-completeness for $k=O(1)$. $\endgroup$
    – Mr.
    Feb 18 at 5:40
  • $\begingroup$ 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? $\endgroup$ Feb 18 at 14:43
  • $\begingroup$ How $\oplus L$ interpolates to $\mathsf{NC}^2$ and how it deviates from $PP$ as $k=\Omega(n)$? $\endgroup$
    – Mr.
    Feb 18 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.