<p>I don't think so. Theorem 5.1 of the linked paper shows that, for any fixed k, permanent mod <span class="math-container">$2^k$</span> is <span class="math-container">$\mathsf{\oplus L}$</span>-complete. (I believe the same is true for det mod <span class="math-container">$2^k$</span>.) So it won't be in a smaller class without collapsing the two classes.</p>
<p>Regarding parametrized complexity, <a href="https://arxiv.org/abs/1511.02321" rel="nofollow noreferrer">Curticapean and Xia</a> showed that permanent modulo <span class="math-container">$2^k$</span> is <span class="math-container">$\mathsf{\oplus W[1]}$</span>-hard. So an algorithm of the form you mentioned in the comments, in <span class="math-container">$\mathsf{\oplus SPACE}(f(k) + \log n)$</span> would put it in <span class="math-container">$\mathsf{\oplus TIME}(g(k) poly(n))$</span>.</p>
<p>In terms of runtime, assuming <span class="math-container">$\oplus ETH$</span>, they also show a lower bound on the runtime of <span class="math-container">$n^{\Omega(k / \log k)}$</span>. So one cannot do much better than what is known. (It'd be interesting if someone had closed that <span class="math-container">$\log k$</span> gap in the exponent, but I haven't heard of this.)</p>

CC BY-SA 4.0
2024-09-07T19:40:10.840Z
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$?
Turbo
CC BY-SA 4.0
2023-05-09T23:11:32.473Z
2023-05-09T23:11:32.473Z
Joshua Grochow
<p>Given a <span class="math-container">$0/1$</span> square matrix, the permanent and determinant modulo <span class="math-container">$2^k$</span> is in <span class="math-container">$\oplus P$</span> and <span class="math-container">$\oplus L$</span> respectively for any fixed <span class="math-container">$k$</span>. In fact both are in <span class="math-container">$\oplus L$</span> (in fact in <span class="math-container">$\oplus SPACE(k^2\log n)$</span> by <a href="https://mbraverm.princeton.edu/files/planarCounting.pdf" rel="nofollow noreferrer">https://mbraverm.princeton.edu/files/planarCounting.pdf</a>.</p>
<p>Have there been any improvements?</p>

CC BY-SA 4.0
2023-05-09T19:42:09.423Z
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$)?
Turbo
CC BY-SA 4.0
2023-05-09T20:57:25.957Z
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!
Turbo
CC BY-SA 4.0
2023-05-09T22:55:56.537Z
@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$.
Turbo
<cc.complexity-theory><counting-complexity>
Perm and Det mod $2^k$ - I
Turbo
# Perm and Det mod $2^k$ - I

(Asked by: username_0 on 2023-05-09)

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?

**Tags:** cc.complexity-theory, counting-complexity
> **Comments:**
> **username_0**: 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$)?  
> **username_0**: 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!  
> **username_0**: @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$.  

---

## 1 answers

### Answer by username_1 on 2023-05-09. Score: 2 | Accepted answer

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](https://arxiv.org/abs/1511.02321) 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.)

> **Comments:**
> **username_0**: 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$?  

---

