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 at a time with seed length 2^{O(\sqrt{\log n})}\cdot d^2\log^2(1/\epsilon). This comes quadratically close to optimal dependence in d and \log(1/\epsilon). Improving the dependence on n would imply nontrivial PRGs for \log n-degree F_2-polynomials. The previous PRG by Bogdanov, Dvir, Verbin, and Yehudayoff had an exponentially worse dependence on d with seed length of O(d\log n + d2^d\log(1/\epsilon)).

2. We provide correlation bounds and PRGs against size-n^{\Omega(\log n)} AC0 circuits with either n^{.99} SYM gates (computing an arbitrary symmetric function) or n^{.49} THR gates (computing an arbitrary linear threshold function). Previous work of Servedio and Tan only handled n^{.49} SYM gates or n^{.24} THR gates, and previous work of Lovett and Srinivasan only handled polysize circuits.

3. We give exponentially small correlation bounds against degree-n^{O(1)} F_2-polynomials set-multilinear over some partition of the input into n^{.99} parts (noting that at n parts, we recover all low-degree polynomials). This generalizes correlation bounds against degree-(d-1) polynomials which are set-multilinear over a fixed partition into d blocks, which were established by Bhrushundi, Harsha, Hatami, Kopparty and Kumar.

The common technique behind all of these results is to fortify a hard function with the right type of extractor to obtain stronger correlation bounds. Although this technique has been used in previous work, it relies on the model shrinking to a very small class under random restrictions. Our results show such fortification can be done even for classes that do not enjoy such behavior.