<p>Determinant of integer matrix modulo <span class="math-container">$2$</span> is complete for the class <span class="math-container">$\oplus L$</span>. Is determinant modulo <span class="math-container">$2^k$</span> computable in <span class="math-container">$\oplus L$</span> at any fixed <span class="math-container">$k$</span>?</p>
<p>How about if <span class="math-container">$k=o(n)$</span> where matrix is <span class="math-container">$n\times n$</span>?</p>

CC BY-SA 4.0
2021-02-18T05:15:18.150Z
Have you looked at Valiant's algorithm?
Joshua Grochow
CC BY-SA 4.0
2021-02-18T05:16:24.030Z
Actually I think it provides $n^{O(k)}$ algorithm but no I am not familiar in the workings of it.
Turbo
CC BY-SA 4.0
2021-02-18T05:40:11.880Z
Theorem 1 in https://newtraell.cs.uchicago.edu/files/phd_paper/raghav.pdf provides $\oplus L$-completeness for $k=O(1)$.
Turbo
CC BY-SA 4.0
2021-02-18T14:43:07.567Z
Nice find - I can't believe I forgot about that result, now that I see it I recall him telling me about it in person! It'd be worth updating the question. Also, to your second part about growing k, why this question? Would you be interested in fixed-parameter complexity?
Joshua Grochow
CC BY-SA 4.0
2021-02-18T14:59:19.540Z
How $\oplus L$ interpolates to $\mathsf{NC}^2$ and how it deviates from $PP$ as $k=\Omega(n)$?
Turbo
<complexity-classes><determinant>
On Determinant modulo $2^k$ complexity
Turbo
# On Determinant modulo $2^k$ complexity

(Asked by: username_0 on 2021-02-17)

Determinant of integer matrix modulo $2$ is complete for the class $\oplus L$. Is determinant modulo $2^k$ computable in $\oplus L$ at any fixed $k$?

How about if $k=o(n)$ where matrix is $n\times n$?

**Tags:** complexity-classes, determinant
> **Comments:**
> **username_1**: Have you looked at Valiant's algorithm?  
> **username_0**: Actually I think it provides $n^{O(k)}$ algorithm but no I am not familiar in the workings of it.  
> **username_0**: Theorem 1 in https://newtraell.cs.uchicago.edu/files/phd_paper/raghav.pdf provides $\oplus L$-completeness for $k=O(1)$.  
> **username_1**: Nice find - I can't believe I forgot about that result, now that I see it I recall him telling me about it in person! It'd be worth updating the question. Also, to your second part about growing k, why this question? Would you be interested in fixed-parameter complexity?  
> **username_0**: How $\oplus L$ interpolates to $\mathsf{NC}^2$ and how it deviates from $PP$ as $k=\Omega(n)$?  

---

## 0 answers

