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$ algorithm for perfect matching by Mulmuley, Vazirani, and Vazirani [Combinatorica, 7 (1987), pp. 105–113] and in several other applications. Given a set S and an unknown family F ⊆ 2S with |F| ≤ Z, we present a scheme for assigning polynomially bounded weights to the elements of S using only O(log Z + log |S|) random bits, such that the minimum weight set in F is unique with high probability. This generalizes the solution of Mulmuley, Vazirani, and Vazirani, who use O(S log S) bits, independent of Z. We also provide a matching lower bound for the randomness complexity of this problem. The new weight assignment scheme yields a randomness-efficient RNC² algorithm 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 Karpinski [Proc. IEEE Symposium on Foundations of computer Science, 1987, pp. 166–172], who present an NC³ algorithm when Z is polynomial and improves the running time in this case. The worst-case randomness complexity of our algorithm is O(n log (m/n)) random bits improving on the previous bound of O(m log n). Our scheme also gives randomness-efficient solutions for several problems where unique element isolation is used, such as $RNC$ algorithms for variants of matching and basic problems on linear 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 ⊆ ⊕ P and Few P ⊆ C₌ P.