RANDOMNESS-OPTIMAL UNIQUE ELEMENT ISOLATION WITH APPLICATIONS TO PERFECT MATCHING AND RELATED PROBLEMS

In this paper, we precisely characterize the randomness complexity of the unique element isolation problem, a crucial step in the RNC algori thm for perfect matching by Mulmuley, Vazirani, and Vazirani [Combinat orica, 7 (1987), pp. 105-113] and in several other applications. Given a set S and an unknown family F subset of or equal to 2(S) with \F\ l ess than or equal to Z, we present a scheme for assigning polynomially bounded wrights to the elements of S using only O(log Z + log \S\) ra ndom bits, such that the minimum weight set in F is unique with high p robability. This generalizes the solution of Mulmuley, Vazirani, and V azirani, who use O(S log S) bits, independent of Z. We also provide a matching lower bound for the randomness complexity of this problem. Th e new weight assignment scheme yields a randomness-efficient RNC(2) al gorithm for perfect matching which uses O(log Z + log n) random bits, where Z is any given upper bound on the number of perfect matchings in the input graph. This generalizes the result of Grigoriev and Karpins ki [Proc. IEEE Symposium on Foundations of Computer Science, 1987, pp. 166-172], who present an NC3 algorithm when Z is polynomial and impro ves the running time in this case. The worst-case randomness complexit y of our algorithm is O(n log(m/n)) random bits improving on the previ ous bound of O(m log n). Our scheme also gives randomness-efficient so lutions for several problems where unique element isolation is used, s uch as RNC algorithms for variants of matching and basic problems on l inear matroids. We obtain a randomness-efficient random reduction from SAT to USAT, the language of uniquely satisfiable formulas, which can be derandomized in the case of languages in Few P to yield new proofs of the results Few P subset of or equal to + P and Few P subset of or equal to C = P.