@article {17648, title = {Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems}, journal = {SIAM Journal on Computing}, volume = {24}, year = {1995}, month = {1995///}, pages = {1036 - 1036}, abstract = {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{\textendash}113] and in several other applications. Given a set $S$ and an unknown family $\mathcal{F} \subseteq 2^{S}$ with $|\mathcal{F}| \leq 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 $\mathcal{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^{2}$ 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{\textendash}172], who presentan $NC^{3}$ 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 \subseteq \oplus P$ and Few $P \subseteq C_{=} P$.}, isbn = {00975397}, doi = {10.1137/S0097539793250330}, url = {http://link.aip.org/link/SMJCAT/v24/i5/p1036/s1\&Agg=doi}, author = {Chari,Suresh and Rohatgi,Pankaj and Srinivasan, Aravind} }