@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}
}
