We study pseudorandom bit generators for Boolean linear sums modulo a fixed
integer $M$. A distribution $X\in\{0,1\}^n$ $\varepsilon$-fools these tests if, for
every $a\in\mathbb{Z}_M^n$, the distribution of
\[
\sum_{i=1}^n a_iX_i \pmod M
\]
is $\varepsilon$-close in statistical distance to the corresponding distribution
under independent uniform bits.

Lovett, Reingold, Trevisan, ... more >>>

We unconditionally prove there exists a promise problem in promise ZSUBEXP that cannot be solved in promise RP.
The proof technique builds upon Kabanets' easy witness method [Kab01] as implemented by Impagliazzo et. al [IKW02], with a separate diagonalization carried out on each of the two alternatives in the ... more >>>