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 >>>

We prove that the XOR of $k$ majorities on disjoint blocks of \(\ell\) bits has correlation at most \((2d/\sqrt{\ell})^k\) with every degree-\(d\) polynomial over \(\mathbb F_2\). By known techniques, this implies pseudorandom generators with polylogarithmic seed length for low-degree polynomials over $\mathbb F_2$ and for alternating circuits with parity ... more >>>