An $(n,k)$-bit-fixing source is a distribution $X$ over $\B^n$ such that
there is a subset of $k$ variables in $X_1,\ldots,X_n$ which are uniformly
distributed and independent of each other, and the remaining $n-k$ variables
are fixed. A deterministic bit-fixing source extractor is a function $E:\B^n
\ar \B^m$ which on ... 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 >>>