# Perm and Det mod $2^k$ - I

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.

Have there been any improvements?

• I don't think permanent mod $2$ is complete for $\oplus P$ since it is in $P$. I was thinking $\oplus SPACE(f(k)+\log(n))$ form where $f(k)=O(k^c)$ where $c<3$ (perhaps $c=1$)? Or $\oplus SPACE(f(k)\log(n))$ form where $f(k)=O(k^c)$ where $c<2$ (perhaps $c=1$)? Commented May 9, 2023 at 19:42
• Note if space is not a constraint we can get the mod $2^k$ result in $n^{O(k)}$ time and I would expect at least an $\oplus SPACE(k\log n)$ algorithm to exist! Commented May 9, 2023 at 20:57
• @JoshuaGrochow I think not since by the result in the paper permanent mod $2^2$ is in $\oplus SPACE(\log n)$ and hence in $\oplus L$. Commented May 9, 2023 at 22:55

I don't think so. Theorem 5.1 of the linked paper shows that, for any fixed k, permanent mod $$2^k$$ is $$\mathsf{\oplus L}$$-complete. (I believe the same is true for det mod $$2^k$$.) So it won't be in a smaller class without collapsing the two classes.
Regarding parametrized complexity, Curticapean and Xia showed that permanent modulo $$2^k$$ is $$\mathsf{\oplus W[1]}$$-hard. So an algorithm of the form you mentioned in the comments, in $$\mathsf{\oplus SPACE}(f(k) + \log n)$$ would put it in $$\mathsf{\oplus TIME}(g(k) poly(n))$$.
In terms of runtime, assuming $$\oplus ETH$$, they also show a lower bound on the runtime of $$n^{\Omega(k / \log k)}$$. So one cannot do much better than what is known. (It'd be interesting if someone had closed that $$\log k$$ gap in the exponent, but I haven't heard of this.)
• On a possible converse existence... if $\#ETH$ is false in such that may be we have a quasiP algorithm for $\#SAT$ (say $n^{O(\log n)}$ time and space algorithm), then do we have a $c^{O(k)}$ algorithm for permanent modulo $2^k$? Commented Sep 7 at 19:40