  Many randomized algorithms can be derandomized efficiently using either the
method of conditional expectations or probability spaces with low (almost-)
independence. A series of papers, beginning with Luby (1993) and continuing
with Berger & Rompel (1991) and Chari et al. (2000), showed that these
techniques can be combined to give deterministic parallel algorithms for
combinatorial optimization problems involving sums of $w$-juntas. We improve
these algorithms through derandomized variable partitioning and a new code
construction for fooling Fourier characters over $GF(2)$. This reduces the
processor complexity to essentially independent of $w$ while the running time
is reduced from exponential in $w$ to linear in $w$.
  As a key subroutine, we give a new algorithm to generate a probability space
which can fool a given set of neighborhoods. Schulman (1992) gave an NC
algorithm to do so for neighborhoods of size $w \leq O(\log n)$. Our new
algorithm is NC1, with essentially optimal time and processor complexity, when
$w = O(\log n)$; it remains NC up to $w = \text{polylog}(n)$. This answers an
open problem of Schulman.
  One major application of these algorithms is an NC algorithm for the
Lov\'{a}sz Local Lemma. Previous NC algorithms, including the seminal algorithm
of Moser & Tardos (2010) and the work of Chandrasekaran et. al (2013), required
that (essentially) the bad-events could span only $O(\log n)$ variables; we
relax this to $\text{polylog}(n)$ variables. We use this for an $\text{NC}^2$
algorithm for defective vertex coloring, which works for arbitrary degree
graphs.
