Given a prime $p$, an integer $0\le n\le p-1$, and a divisor $q\mid(1+p+p^2)$, we compute $n!\bmod p$ in expected bit complexity $\widetilde{O}\left(q^c+\frac{\sqrt{p}}{q^{1/4}}\right)$ for some absolute constant $c\ge1$. More generally, the construction applies when $q\mid\Phi_r(p)$, where $\Phi_r$ is the $r$-th cyclotomic polynomial and $r$ is any fixed odd prime power. Combining ... more >>>

We construct improved pseudorandom generators for read-$k$ oblivious branching programs with a known reading sequence.
For width-$w$ branching programs over $n$ variables, and designated error $\varepsilon$, our generator has seed length
$$\mathcal{O}\left(n^{1-\frac{1}{2k-1}}\log n\left(k\log w+\log\frac{n}{\varepsilon}\right)\right).$$
This improves upon the previous state-of-the-art due to Gurjar and Volk (ACM ToCT 2020), that has ... more >>>

We study interactive proofs when the prover and the verifier access the same underlying data through independent noisy views. The noise is \emph{persistent} for each party: each location is corrupted once, and repeated queries to the same location return the same corrupted value. We introduce two models in this setting: ... more >>>