# On space complexity of permanent modulo $2^t$?

1. We know from here that permanent of $0/1$ matrix modulo $2^t$ is in $DTIME(n^{t+3})$ and hence in $P$. My question is whether permanent of $0/1$ matrix modulo $2^t$ is in $L$ as well or is the current best algorithm outside $NL$?

2. Suppose deciding if permanent of $\{0,1\}$ matrices is greater than $r\in\Bbb R$ has a $BPP$ algorithm which uses only logarithmic space then is there a name for the complexity class of such a situation? Clearly it cannot be $BPP\cap L$ since $BPP\cap L=L$ would mean $PP=L$ ands the algorithm is deterministic which it clearly is not?

• Already for $t=1$, computing the permanent mod 2 is the same as computing the determinant mod 2, which is $\oplus L$-complete, which means it is not known to be in NL. – Emil Jeřábek May 8 '17 at 12:04
• @EmilJeřábek Thank you and is it $\oplus L$-complete for $t>1$ as well? – 1.. May 8 '17 at 12:21
• I think with Emil's observation and the result of Braverman, Kukarni and Roy computing Permanent mod $2^t$ for fixed $t$ is $\oplus L$-complete. See pdfs.semanticscholar.org/07ad/… – Nikhil May 8 '17 at 13:20
• en.wikipedia.org/wiki/BPL_%28complexity%29 – Emil Jeřábek May 8 '17 at 15:18