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 work by Luby (1988) and continuing with Berger & Rompel (1991) and Chari et al. (1994), 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. This reduces the processor complexity to essentially independent of  w  while the running time is reduced from exponential in  w  to linear in  w.  For example, we improve the time complexity of an algorithm of Berger & Rompel (1991) for rainbow hypergraph coloring by a factor of approximately log 2   n  and the processor complexity by a factor of approximately  m  ln 2 .   As a major application of this, we give an NC algorithm for the Lovasz 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 allowing polylog( n ) variables. As two applications of our new algorithm, we give algorithms for defective vertex coloring and domatic graph partition.   One main sub-problem encountered in these algorithms is to generate a probability space which can "fool" a given list of  GF (2) Fourier characters. Schulman (1992) gave an NC algorithm for this; we dramatically improve its efficiency to near-optimal time and processor complexity and code dimension. This leads to a new algorithm to solve the heavy-codeword problem, introduced by Naor & Naor (1993), with a near-linear processor complexity ( mn ) 1+ o (1) .
['David G. Harris']
Deterministic parallel algorithms for fooling polylogarithmic juntas and the lovász local lemma