2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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$)? $\endgroup$
    – Turbo
    Commented May 9, 2023 at 19:42
  • 1
    $\begingroup$ 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! $\endgroup$
    – Turbo
    Commented May 9, 2023 at 20:57
  • $\begingroup$ @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$. $\endgroup$
    – Turbo
    Commented May 9, 2023 at 22:55

1 Answer 1

Reset to default
2
$\begingroup$

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.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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$? $\endgroup$
    – Turbo
    Commented Sep 7 at 19:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.