Improved parallel derandomization via finite automata with applications

A central approach to algorithmic derandomization is to construct probability distributions with small support that "fool" randomized algorithms, often enabling efficient parallel (NC) implementations. An abstraction of this idea is fooling polynomial-space statistical tests computed via finite automata (Sivakumar 2002); this encompasses a wide range of properties including $k$-wise independence and sums of random variables. We present new parallel algorithms to fool automata, with significantly reduced processor complexity. Briefly, our approach is to iteratively sparsify distributions via work-efficient lattice discrepancy rounding, while tracking an aggregate weighted error that is determined by the Lipschitz value of the statistical tests. We illustrate with applications to the Gale-Berlekamp Switching Game and approximate MAX-CUT via SDP rounding. These involve several optimizations, including truncating the state space of the automata and using FFT-based convolutions to compute transition probabilities efficiently.