We prove a time hierarchy theorem for the promise-BPTIME. This is considered to be a folklore problem and was thought to follow from the existence of complete problems or through direct diagonalization. We observe that neither argument carries through in some immediate way in the promise version. However, the hierarchy ... more >>>

For any constant $\alpha > 0$, we construct an explicit pseudorandom generator (PRG) that fools $n$-variate decision trees of size $m$ with error $\epsilon$ and seed length $(1 + \alpha) \cdot \log_2 m + O(\log(1/\epsilon) + \log \log n)$. For context, one can achieve seed length $(2 + o(1)) \cdot ... more >>>

We establish new correlation bounds and pseudorandom generators for a collection of computation models. These models are all natural generalizations of structured low-degree $F_2$-polynomials that we did not have correlation bounds for before. In particular:

1. We construct a PRG for width-2 $poly(n)$-length branching programs which read $d$ bits ... more >>>