2026-07-21T20:02:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24538 2025-12-16T14:00:32Z ddc:004 open_access

Improved Parallel Derandomization via Finite Automata with Applications Giliberti, Jeff Harris, David G. Parallel Algorithms Derandomization MAX-CUT Gale-Berlekamp Switching Game A central approach to algorithmic derandomization is the construction of small-support probability distributions 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 STOC'02]; this encompasses a wide range of properties including k-wise independence and sums of random variables. We present new parallel algorithms to fool finite-state automata, with significantly reduced processor complexity. Briefly, our approach is to iteratively sparsify distributions using a work-efficient lattice rounding routine and maintain accuracy by tracking an aggregate weighted error that is determined by the Lipschitz value of the statistical tests being fooled. We illustrate with improved applications to the Gale-Berlekamp Switching Game and to approximate MAX-CUT via SDP rounding. These involve further several optimizations, such as the truncation of the state space of the automata and FFT-based convolutions to compute transition probabilities efficiently. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeff Giliberti and David G. Harris 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.70 urn:nbn:de:0030-drops-245381 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.70 eng https://creativecommons.org/licenses/by/4.0/legalcode