<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>Suppose we know permanent and determinant mod <span class="math-container">$2^{k-1}$</span>. Then</p>
<ol>
<li><p>what is the best complexity class we would be in for each of permanent and determinant modulo <span class="math-container">$2^k$</span> when <span class="math-container">$k=\Omega(\log n)$</span>?</p>
</li>
<li><p>What about for permanent and determinant mod <span class="math-container">$2^{k+r}$</span> where <span class="math-container">$r=O(1)$</span>?</p>
</li>
<li><p>what is the best time complexity known when <span class="math-container">$k=\Omega(\log n)$</span>?</p>
</li>
</ol>
<p><strong>Conjecture</strong>: 1. and 2. are in <span class="math-container">$\oplus SPACE(\log n)$</span> and 3. is in <span class="math-container">$O(n^c)$</span> at a fixed <span class="math-container">$c\geq1$</span>.</p>

CC BY-SA 4.0
2023-08-04T00:08:21.417Z
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)
Joshua Grochow
CC BY-SA 4.0
2023-08-05T00:03:48.360Z
@JoshuaGrochow Yes.
Turbo
<cc.complexity-theory><complexity-classes><logspace>
Perm and Det mod $2^k$ - II
Turbo
# Perm and Det mod $2^k$ - II

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

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 about for permanent and determinant mod $2^{k+r}$ where $r=O(1)$?
3. what is the best time complexity known when $k=\Omega(\log n)$?

**Conjecture**: 1. and 2. are in $\oplus SPACE(\log n)$ and 3. is in $O(n^c)$ at a fixed $c\geq1$.

**Tags:** cc.complexity-theory, complexity-classes, logspace

> **Comments:**
> **username_1**: 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)  
> **username_0**: @JoshuaGrochow Yes.  

---

## 0 answers

