We construct an explicit hitting set generator (HSG) for ordered read-once branching programs of width 4. For every length $n$ and every $\varepsilon \in (0,1)$, every width-4 length-$n$ program that accepts more than an $\varepsilon$ fraction of its inputs accepts at least one output of the generator, and the seed ... more >>>

We use this framework to construct HSGs for read-once CNFs and read-once CNFs with parities. For formulas on $n$ variables with density at least $\varepsilon$, our generators use $O(\log(n/\varepsilon))$ seed bits. This bound is optimal up to a constant factor. Applying the hitting reduction of Gopalan, Meka, Reingold, Trevisan, and ... more >>>

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