Deterministic Parallel Algorithms for Bilinear Objective Functions

摘要

Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low independence. A series of papers, beginning with work by Luby (1988), showed that in many cases these techniques can be combined to give deterministic parallel (NC) algorithms for a variety of combinatorial optimization problems, with low time- and processor-complexity. We extend and generalize a technique of Luby for efficiently handling bilinear objective functions. One noteworthy application is an NC algorithm for maximal independent set. On a graph G with m edges and n vertices, this takes (log2n) time and (m+n)no processors, nearly matching the best randomized parallel algorithms. Other applications include reduced processor counts for algorithms of Berger (SIAM J Comput 26:1188-1207, 1997) for maximum acyclic subgraph and Gale-Berlekamp switching games. This bilinear factorization also gives better algorithms for problems involving discrepancy. An important application of this is to automata-fooling probability spaces, which are the basis of a notable derandomization technique of Sivakumar (In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp 619-626, 2002). Our method leads to large reduction in processor complexity for a number of derandomization algorithms based on automata-fooling, including set discrepancy and the Johnson-Lindenstrauss Lemma.