Complexity of permanent modulo prime Given $M\in\Bbb Z^{n\times n}$ with $O(n)$ bit entries (could be all in $\{0,1\}$), $p$ a prime of $O(n^\alpha)$ bits for some $\alpha\in(0,1]$ and a $c,d\in\Bbb Z$ with $0\leq c&lt;d&lt;p$, is 'Is $\mathsf{Perm}(M)\bmod p\in\{c,\dots,d\}$?' $\mathsf{PP}$-complete?

What if $p$ is $O(\log n)$ bits or even smaller?

Without the ${}\bmod p$ it is known to be $\mathsf{PP}$-complete.
First, the permanent of an $n\times n$ integer matrix with $O(n)$-bit coefficients is an integer with $O(n^2)$ bits, hence if we know it modulo an integer with $\Omega(n^2)$ bits (with the implied constant depending on the constant in the input bit size), we know it outright.

Your problem with $p$ allowed to have $O(\log n)$ bits is PP-hard under polynomial-time Turing reductions: in order to compute permanent, just compute it modulo every prime below $cn^2$, and use the Chinese remainder theorem to find its value modulo the product of these primes, which is roughly $e^{cn^2}$. By the above, this provides the true value of the permanent for suitable $c$.

There is a serious obstacle to using your problem for primes with $\omega(\log n)$ bits: any reduction to this problem must in particular produce a prime number, and we know of no provably correct deterministic way of computing large primes significantly faster than brute force.

But if you allow randomized reductions, or say, reductions with free access to solutions of the search problem “given $x$, find a prime $p$ such that $x\le p\le2x$”, then you can reduce the number of oracle queries in the reduction of permanent I gave above by using a smaller number of larger primes: if you allow primes $p$ with $m(n)$ bits, you can do away with about $n^2/m(n)$ oracle calls.

For $m(n)=n^\alpha$ with constant $\alpha$, you can use padding to reduce the number of queries to $1$, i.e., to get a randomized many-one reduction: given the input $n\times n$ matrix $M$, find a prime $p$ of at least $n^2$ bits, and let $M'$ be the matrix $M$ padded with diagonal $1$s to dimension $n'\times n'$, where $n'^\alpha\ge\log p$. Then ask for the permanent of $M'$ modulo $p$.