Given a $0/1$ square matrix, the permanent and determinant modulo $2^k$ is in $\oplus P$ and $\oplus L$ respectively for any fixed $k$. In fact both are in $\oplus L$ (in fact in $\oplus SPACE(k^2\log n)$ by https://mbraverm.princeton.edu/files/planarCounting.pdf.

Suppose we know permanent and determinant mod $2^{k-1}$. Then

  1. what is the best complexity class we would be in for each of permanent and determinant modulo $2^k$ when $k=\Omega(\log n)$?

  2. what is the best time complexity known when $k=\Omega(\log n)$?

  • $\begingroup$ Are you asking: given as input (A,z) where A is an n x n integer matrix and z = det(A) mod 2^{k-1}, compute det(A) mod 2^k? (And similar for perm) $\endgroup$ Aug 4, 2023 at 0:08
  • $\begingroup$ @JoshuaGrochow Yes. $\endgroup$
    – Turbo
    Aug 5, 2023 at 0:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.