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 \log_2 m + O(\log(1/\epsilon) + \log \log n)$ using well-known constructions and analyses of small-bias distributions, but such a seed length is trivial when $m \geq 2^{n/2}$. By combining our new PRG with work by Chen and Kabanets (TCS 2016), we get an explicit PRG that fools circuits of size $2.99\cdot n$ over the $U_2$ basis with error $2^{-\Omega(n)}$ and seed length $(1 - \Omega(1)) \cdot n$.

Our approach for fooling decision trees is to develop a new variant of the classic concept of almost $k$-wise independence, which might be of independent interest. We say that a distribution $X$ over $\{0, 1\}^n$ is $k$-wise $\epsilon$-probably uniform if every Boolean function $f$ that depends on only $k$ variables satisfies $\mathbb{E}[f(X)] \geq (1 - \epsilon) \cdot \mathbb{E}[f]$. We show how to sample a $k$-wise $\epsilon$-probably uniform distribution using a seed of length $(1 + \alpha) \cdot k + O(\log(1/\epsilon) + \log \log n)$.