BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1359
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Randomness-Optimal Unique Element Isolation, With Applications to 
        Perfect Matching and Related Problems
AUTHOR:: Chari, Suresh
AUTHOR:: Rohatgi, Pankaj 
AUTHOR:: Srinivasan, Aravind
DATE:: June 1993
PAGES:: 22
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 due to Mulmuley, Vazirani \& Vazirani[21] and in several 
other applications. Given a set $S$ and an unknown family 
$\cal F \subseteq$ $2^{S}$ with $|\cal F| \leq$ $Z$, we present a scheme to 
assign polynomially bounded weights to the elements of $S$, using only 
$O(\log Z + \log |S|)$ ransom bits, such that the minimum weight set in 
$\cal F$ is unique with high probability. This generalizes and improves the 
results of Mulmuley, Vazirani \& Vazirani who give a scheme which uses 
$O(S \log S)$ random bits independent of $Z$. We also prove a matching lower 
bound for the randomness complexity of this problem. This 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 \& Karpinski[11] who present an $NC^{3}$ 
algorithm when $Z$ is polynomially bounded and also gives an improvement on 
the running time in this case. The worst-case randomness complexity of our 
algorithm is $O(n \log (m/n))$ random bits, as opposed to the previous bound 
of $O(m \log n)$ bits. Our technique also gives randomness-efficient 
solutions for several problems in which the unique element isolation tool is 
used, such as $RNC$ algorithms for variants of matching and basic problems on 
linear matroids such as matroid intersection and matroid matching. We also 
obtain a randomness-efficient alternative to the random reduction from $SAT$ 
to $USAT$, the language of uniquely satisfiable formulas, due to Valiant and 
Vazirani[32]. This reduction can be derandomized in the case of languages in 
$F ew P$ to yield new proofs of the results $F ew P \subseteq \oplus P$ and 
$F ew P \subseteq C_{=} P$. 
END:: CORNELLCS//TR93-1359
BODY::
Randomness-Optimal Unique Element Isolation,
With Applications to Perfect Matching and
Related Problems
Suresh Chari*
Pankaj Rohatgi**
Aravind Srinivasan***
TR 93-1359
June1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*Supported in part by NSF grant CCR-91 23730.
**Supported in part by NSF grant CCR-9123730 and an IBM Graduate Fellowship.
Also supported in part by the United States Army Research Office through the Army
Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM),
Mathematical Sciences Institute of Cornell University Contract DAAL03-91 -C-0027.
***Supported in part by NSF PYl award CCR-89-96272 with matching support from
UPS and Sun Microsystems, and by an IBM Graduate Fellowship.
R?andomness-Optimal Unique Element Isolation, with
Applications to Perfect Matching and ?elated Problems
Suresh Cliari*			Pankaj Rohatgit			Aravind Sflnivasant
Department of Computer Science
Cornell University
Ithaca, NY 14853
Abstract
In this paper, we precisely characterize the randomness complexity of the unique ele-
ment isolation problem, a crucial step in the RNC algorithm for perfect matching due to
Mulmuley, Vazirani ? VaziraniJ?4 and in several other applications. Given a set 5 and
an unknown family ? C 2? with j?j < Z, we present a scheme to assign polynomially
bounded weights to the elements of 5, using only O(log Z + log jSj) random bits, such
that the minimum weight set in ? is unique with high probability. This generalizes and
improves the results of Mulmuley, Vazirani ? Vazirani who give a scheme which uses
0(5 log 5) random bits independent of Z. We also prove a matching lower bound for the
randomness complexity of this problem. This new weight assignment scheme yields a
randomness--Hefficient RNC2 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 ? Karpinski[11] who present an
NC3 algorithm when Z is polynomially bounded and also gives an improvement on the
running time in this case. The worst--Hcase randomness complexity of our algorithm is
O(nlog(m/n)) random bits, as opposed to the previous bound of O(mlogn) bits. Our
technique also gives randomness--Hefficient solutions for several problems in which the
unique element isolation tool is used, such as RNC algorithms for variants of match-
ing and basic problems on linear matroids such as matroid intersection and matroid
matching. We also obtain a randomness--Hefficient alternative to the random reduction
from SAT to USAT, the language of uniquely satisfiable formulas, due to Valiant and
Vaziranij32j. This reduction can be derandomized in the case of languages in FewP to
yield new proofs of the results FewP c e? and FewP c ?p
Supported in part by NSF grant CCR-9123730.
tSupported in part by by NSF grant CCR-9123730 and an IBM Graduate Fellowship. Also supported
in part by the United States Army Research Office through the Army Center of Excellence for Symbolic
Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University
Contract DAALo3-91-C-oo27.
tsupported in part by NSF PYl award CCR-89-96272 with matching support from UPS and Sun Mi-
crosystems, and by an IBM Graduate Fellowship.
1 Introduction
Given a graph C, a matching in G is a subset of the edges such that no two edges in the
subset are incident on the same vertex. A maximvm matching in G is a matching in C of
maximum cardinality, and a perfect matching is a special type of maximum matching in
which each vertex is covered by an edge, z. e., each vertex is matched, Finding a perfect
matching, if any, in a graph is one of the fundamental problems in combinatorial optimiza-
tion. While its sequential complexity has been well-studied (Lovasz & Plummer [19]), a
big open question in the theory of parallel algorithms is whether a perfect matching can
be found or even detected in NC. Due to its importance, considerable effort has been
devoted towards developing parallel algorithms for the perfect matching problem. For in-
stance, sublinear time parallel algorithms for general graphs (Goldberg, Plotkin & Vaidya
[10], Vaidya [31], Grover [12]) and for bipartite graphs (Goldberg, Plotkin, Shmoys & Tar-
dos [9]) are known. NC algorithms have also been developed for special classes of graphs
such as co--Hcomparability graphs (Kozen, Vazirani & Vazirani [17]), strongly chordal graphs
(Dahlhaus & Karpinski [7]), graphs with polynomially many perfect matchings (Grigoriev
& Karpinski [11]), and planar bipartite graphs (Miller & Naor [20]). A very successful
approach for the general problem has been to use randomness: both Monte Carlo RNC
algorithms (Karp, Upfal & Wigderson [14], Mulmuley, Vazirani & Vazirani [21]) and Las
Vegas RNC algorithms (Karloff [13]) have been developed.
In this paper, we investigate the parallel randomness complexity of perfect matching and
related problems, i. e., the amount of randomness required to solve them in parallel. For
perfect matching we present an RNC2 algorithm which uses O(log Z + log n) random bits
where Z is any given upper bound on IMat(G)I, the number of perfect matchings in the
graph G. This improves and generalizes the result of Grigoriev & Karpinski [11] who give
an NC3 algorithm when Z is polynomially bounded. Since a graph on n vertices with m
edges can have at most (2m/n)? perfect matchings, the worst case randomness complexity
of our algorithm is O(nlog(m/n)) which improves on the previous bound of O(mlogn)
due to Mulmuley, Vazirani & Vazirani [21]. Thus by linking the randomness complexity of
this problem to the number of perfect matchings, we unify and generalize previous results,
while also improving on them. In special cases, e.g., K3,3--Hfree graphs, the number of perfect
matchings in the graph can be computed in NC2 (see for example Vazirani [33] and also
the work of Kastelyn[15] and Little [18]); in general, if no good upper bound on IMat(G)I
is known, our results yield an RNC3 algorithm to find a perfect matching which uses at
most O(log IMat(G) I) random bits with high probability, if the input graph has at least one
matching. This is a significant reduction if 0 < [Mat(G) <? (2m/n)?. All these results are
obtalned from a randomness--Hoptimal generalization of the Isolating Lemma, a tool used to
isolate a perfect matching in the RNC algorithm of Mulmuley, Vazirani and Vazirani[21].
Since this abstract and powerful tool has several applications such as to basic problems on
2
linearly representable matroids, variants of matching and random reductions in structural
complexity theory, our generalization results in randomness--Hefficiency in these settings as
well.
Given a set S=?x1,x2,... , xNl and an nnknown family ? C 2?, the Isolating Lemma
of [21] shows that if the Xj `5 are independently assigned weights uniformly at random from
the range [1, 2,... , 2N?, then with probability at least 1/2, the minimum weight set in
? is unique. This weight assignment scheme clearly requires ?(N log N) random bits and
an question left open in the original paper was whether the assumption that the weights
be assigned independently is necessary. Our scheme generalizes this as follows: given an
upper bound Z on ??, we assign polynomially bounded weights to the Xj'5 using only
O(log Z + log N) random bits and achieve the same result. In the worst case --H 2N)
our scheme needs 0(N) random bits as compared to G(N log N); more importantly, for
smaller Z, we get much better randomness complexity. Also, since even in the worst case
we assign polynomial weights to N different random variables using 0(N) random bits,
the weight assignments are not independent, thus settling the open question of [21]. Our
scheme provides an explicit construction of a collection of (Nz)0(') weight assignments
such that, for every family ? of size at most Z, at least one (in fact, at least 50%) of
these assignments makes the minimum weight subset in ? unique. Such a collection of
size O(NZ) is guaranteed to exist by applying Adleman's technique [1] to the original
Isolating Lemma, and thus this is one of the few instances where Adleman's result can
be made constructive with only a polynomial blowup in size. Iufthermore, we also show
that our weight assignment scheme is optimal by proving a matching lower bound for this
generalization, ?.e., any scheme which assigns polynomial weights to the Xj'5 must use
?(log Z + log N) random bits even to achieve isolation with only nonzero probability.
This randomness--Hefficient generalization of the isolation process can be directly plugged
into the settings where the original Isolating Lemma has been used to obtain randomness
efficiency. Besides the new algorithm for perfect matching we get randomness--Hefficient al-
gorithms for variants of perfect matching such as exact matching and maximum matching.
We get RNC2 algorithms for exact and maximum matching which use 0(log Z + log n) ran-
dom bits, where Z is a 9iven upper bound on the number of exact matchings and maximum
matchings respectively. Matroid intersection and matroid matching are generalizations of
bipartite and general graph matching, and the Isolating Lemma has been used to obtain
RNC2 algorithms for these basic problems on linearly representable matroids (Narayanan,
Saran & Vazirani [22]). Here, by obtaining good bounds on the size of the family on which
the Isolating Lemma operates, we obtain significant savings in the number of random bits
required. The randomness complexities of our aigorithms for matroids, when specialized
to the case of matching, yield precisely our results on matching. In particular, we give
NC2 algorithms for these problems on matroids under certain restrictions which in the
3
case of graph matching correspond exactly to a polynomial bound on the number of perfect
matchings. This generalizes the results of [11] to matroids and also generalizes a result due
to Tiwari[28].
Another important application of the Isolating Lemma is to obtain an alternative to the
Valiant & Vazirani random reduction [32] from SAT to USAT. Our generalization yields
a new random reduction whose randomness complexity is logarithmic in the number of
satisfying assignments. The worst case complexity matches the best--Hknown bound of 0(n)
(Tami [26]) and also directly gives new proofs of the results that FewP, where the number
of satisfying assignments is polynomially bounded, is contained in eP (Cal & Hemachandra
[3]) and in ?P (K5bler, Sch5ning, Toda & Toran [16]).
This paper is organized as follows: In Section 2 we describe the weight assignment
scheme and also show that it has optimal randomness complexity. Section 3 lists the
applications of the new tool to perfect matching and its variants. Applications to problems
on linearly representable matroids and random reductions in structural complexity are listed
in Section 4.
2 The Generalized Isolating Lemma
In this section we present our randomness--Hefficient generalization of the Isolating Lemma
and also show its optimality by proving a matching randomness complexity lower bound
for this problem. We start with a formal statement of the Isolating Lemma:
Definition A set system (5, ?) consists of a finite set 5 = ....... , xNl and a family ? of
subsets of 5. A weight assignment w = ....... , wN? to the elements xI...., xN, extends
naturally to sets in ? with w(5j) = ??iESj ?1
The crux of the RNC2 algorithm of Mulmuley, Vazirani & Vazirani is the following prob-
abilistic tool:
Lemma 1 [Isolating Lemma] [21] Let (5, ?) be any set system. If the elements Xj
of 5 are assigned random weights uniformly and independently from ?1,2,... , 2N? then,
with probability at least 1/2, there will be a unique minimum weight set in ?
Two features make the isolating lemma widely applicable. First, the isolation process works
for arbitrary and unknown families ? and second, isolation is achieved by assigning only
polynomial weights. For example, in the bipartite perfect matching problem where 5 is the
set of edges and ? is the collection of perfect matchings, the first feature allows isolation to
be done in RNC without any knowledge of the perfect matchings and the second ensures
that a matching can be found by inverting a matrix with polynomial sized entries [21].
4
2.1 New Isolation Scheme
We prove a randomness--Hefficient generalization of the Isolating Lemma which also assigns
polynomial weights and which depends only on any given upper bound Z on the size of the
unknownfamily ?. The motivation for this generalization is that in several settings where
the Isolating Lemma has been used to obtain randomized algorithms in the general case,
we have deterministic solutions when the number of solutions is small[11, 28, 3]. These
deterministic solutions have been obtained by techniques that are specialized to each case
and our aim is to obtain them by carefully parametrizing the randomness complexity of the
algorithms for the general case. To do this we prove the following generalization:
Lemma 2 [Generalized Isolating Lemma] Let (S, F) be any set system and let Z be
agiven upperbound on the size of the unknownfamily?. There is a simple scheme which
usesO(log Z + log N) random bits to assignintegerweights to theXj`5 in the range [0,N7)
such that with probability at least 1/4, there is a unique minimum weight set in f.
PROOF. We outline a four-step process for assigning weights to the Xj'5 and prove that
this scheme has the desired properties. At step j, we assign an intermediate weight w???.
Only steps 2 and 4 are randomized and these steps together use O(log Z + log n) random
bits.
Since ? is unknown we deterministically assign very large weights in Step 1 so that
every set in ? gets a distinct weight.
[step 1: For each i, set w1?1? = 2i'.
Under w?1?, sets in ? have distinct weights in (1,2,... , 2N+ly Clearly, if z  2N+1,
the same property should be obtainable with much lower weights. Since ? is unknown, a
deterministic strategy for reducing weights may fail; instead, we use a randomized strategy.
Step 2: Choose m uniformly at random from (1,2,... ,(2NZ2)2y. For each i, define
mod m.
Step 2 requires O(log Z+log N) random bits. Under w?2?, the Z or fewer sets in ? have
weights in the interval [0, min(N(2NZ2)2, 2N+1)], which is a big improvement for small
values of Z. We now claim that with good probability, these weights are also distincL
Claim 1 With probability at least 1/2, all sets in ? have distinct weights under w?2?.
PROOF. Suppose ? = ....... , S??J where k <Z. Consider the (unknown) integer
I = fi ( w?1)(St') --H w(1)(S?) ).
1<i<j<k
5
Clearly the properties of w?1? ensure that I # 0 and that I < 22NZ2 The following
number-theoretic proposition, together with the Chinese Remainder Theorem establishes
that when m is chosen uniformly from f1, 2,. , (2NZ2)21, the probability that mti is at
least 1/2. Several versions of this proposition appear in the literature; this version is from
[30] and the constant 89 has been improved to 3 by Thrash [27].
Proposition 1 Let L > 89 and let 5 be an? subset of ?1,..., L21 such that 1? > 1L2
Then, the least common multiple of the elements of 5 exceeds 2L
sets in ? have distinct weights under w?2?. If not,
< j. Then we have m			--H w?')(Sj)), which
The
We claim that if m?I, then all
then w?2)(S,) = w(2)(S5) for some i
contradicts the fact that m?I.
Remark: We say that Step 2 succeeds if sets in ? get distinct weights under w?2?.
success probability of this step can be boosted to any constant lesser than 1, since it follows
from the results of de Bruijn [8] that for any fixed p < 1, there exist constants ci and c2
such that if m is picked uniformly at random from ?1, 2,... , NCl zc2 J in Step 2, then Step
2 will succeed with probability at least p.
Note that if Z < NC, then < N4c+3 and with probability at least 1/2, all sets in ?
have distinct weights. Later, we use this strong condition to design an NC2 algorithm to
find all perfect matchings in graphs with at most N0(1) perfect matchings. For larger Z,
the weights are still too big and in Steps 3 and 4 we reduce them further. Step 2 assigns
q-bit weights to the Xj'5 where q = min(N,logm) < min(N,4logz + 2log(2N)). Let
t = [qIlogN].
Step 3: For each i, write wt?2? as q-bit number. Split these bits into t blocks of size
log N bits each as shown. Let bi,j be the number in [0, N --H1] formed by the bits in block
3.
q
: bi,t--Hi ... bi,i b,,0
logN
t--H1
Let w1?3? be the linear form ? bj,j yj over the variables Yo, , Yt--Hi.
i=o
Claim 2 If Step 2 succeeds then the linear forms tJ(3)(Sj) , where Sj E ?, are all distinct.
Proof. Assume that Step 2 succeeds, i.e., that all the weights w?2? (S?) are distinct, where
5> ? ? Note that each wt?3? evaluated at Uk = 2kiogN 0 ? k < t --H 1, is exactly wf.2).
This implies that each w?3)(S>) evaluates to the distinct value w(2)(S>) at Uk = 2kiogN,
0 < k < t --H 1, which implies that the forms w(3)(S>)'s must be distinct. I
6
Note that each w(3)(S?) is a linear forms with coefficients in the range [0, N(N --H 1)].
We will use this property in a crucial way in the analysis of the next and final step.
Step 4: Choose ...... , rt?1 uniformly and independently at random from ?1, 2,... , N5?.
For each i, set w1?4? to be the evaluation of w??3? at Yk = ?k. 0 < k <t --H 1.
We claim that ?(4) achieves the requirements of the Generalized Isolating Lemma.
Clearly, Step 4 requires 5 log N x t = O(log Z + log N) random bits and since Step 2 has
a similar randomness complexity, the overall procedure requires O(log Z + log N) random
bits. It is easy to check that each w,?4? is in [0, N7). Since Step 2 succeeds with probability
at least 1/2, by using C --H ?w(3)(S?) Sj E ?J in the following proposition, we obtain that
the weight assignment w?4? achieves isolation with probability at least 1/4.
Proposition 2 Let C be any collection of distinct linear forms over at most t variables y =
Yo,Yl,.. , Yt--Hi with coefliaents in [0,1,... , N2 --H 1?. Choose a random r = r0...., rt?1 by
assigning each ?j uniformly and independently from [1,2,..., N5?. Then in the assignment
= r there will be a unique linear form with minimum value, with probabihty at least 1/2.
Proof of Proposition: Our proof parallels that of [21]; we define a variable y? to be singular
under an assignment r to the variables y if there exist two minimum valued linear forms in
C under this assignment, having different coefficients of y?. Since all the linear forms in C
are initially distinct, if two linear forms attain the minimum weight then there must exist
some variable which is singular under this assignment.
For each y?, we will upper bound the probability that it is singular. Fix an i and
assume that the variables r?i) = ..... , ?i?1, ?i+1,. . , ri?1 have been assigned the values
aCi) = ..... .,a??1,a?+1,... , aN?1. Under this partial assignment the weight of each linear
form is of the form a+by? where a is the partial weight of the linear form and the coefficient b
is at most N2 --H 1. The family C can be partitioned into at most N2 classes C0,C1,... , CN2?1
based on the coefficient of yi, i.e., forms in Cj have j as the coefficient of y?. By definition, y?
is singular under an assignment . if and only if there are two linear forms from two different
classes in the partition which attain the minimum weight. Consider the probability that the
choice of ?j makes y? singular, conditioned on the partial assignment to the other variables.
Let p> be the minimum partial weight among all the forms in Cj. Note that since all the
forms in a particular class have the same coefficient of y? in their weights, only the forms
with minimum partial weight in each class can possibly attain the minimum overall weight.
Thus the probability that r? makes y? singular is exactly the probability that the minimum
valued element in the list D = [po,pl + r?,p? + ....... ,p?2?i + (N2 --H l)r?] is not unique.
This is clearly bounded by the probability that under a random r? the values of elements
in D are not all distinct. For each pair of elements in D, at most one choice of r, makes
their values equal. Thus
Prob.[?issingularir?i)=a?i)] < Prob.[?l,m: pi+l><r,=p?+rnxr?]
7
< (N22) x Prob.[ pj +1 x r? = Pm + m x
< N2			1			1
-			2			N5 = 2N
Since r? is chosen independently of the other variables r?i) the probability that the
assignment makes y? singular is at most 21N Since this holds for each variable, and there
are at most t < N variables we have
Prob. [ minimum valued form in C is unique] > 1 --H Prob.[ a? y? is singular]
1			1
>1-tx			> -
_			2N			2
Since each of the four steps is elementary the entire weight assignment scheme can be
implemented in NC1. Finally, we note that the Generalized Isolating Lemma provides
an explicit constrtction of (Nz)0(') many weight assignment functions for the ground set
S = fxi,x2,.. .,xNl, such that for any set system (S,?) with j?j < Z, at least half of
these functions will produce a unique minimum weight set in ?. For a given ground set
S, the number of set systems (S, ?) with ? < Z is ?tZ=i (27); hence, the technique of
Adleman [1] combined with the original isolating lemma shows nonconstructively that there
exists a set of o(log(??Z.=1 (27))) = O(NZ) many weight assignment functions such that for
any set system (5, ?) with ? < Z at least one of these functions will produce a unique
minimum weight set in ?.
2.2 A Lower bound for the Isolation problem
We establish a matching lower bound of ?(log Z + log N) random bits on the randomness
complexity of the generalized isolation process, and in fact for the following weaker problem,
thus showing that the randomness complexity of our weight assignment scheme is optimal
to within a constant factor.
Generalized Isolation Let 5 = ....... , xNY and let k be a constant. Assign weights
to the elements of 5 in the range [1, Nk] such that for any family f C 2? of size at most
Z, the minimum weight set in ? is unique with nonzero probability.
First we prove a lower bound of ?(log Z) random bits for any randomized scheme for
the above problem. Each path of such a randomized algorithm defines a weight assignment
f to the Xj `5. The following theorem shows that at least t + 1 different weight assignments
are needed in order to achieve isolation in all possible families of size at most Z, where
t = min([Z2J, [?+i?J) Hence any randomized scheme for generalized isolation must use
?(log t) = ?(log Z) random bits.
Theorem 1 Let fi, f2, , ft be any collection of weight assignments which assign weights
in the range [1,B] to the elements of 5. If t < min(Z2, 2NNB?3), then there exists a family ?
8
of subsets of 5 with ? < 2t < Z, such that the minimum weight subset of? is not unique
under an? of these assignments.
PROOF. Given any I weight assignments we explicitly construct the family ? as follows.
First, for each f?, we compute the "histogram" of the weights of the subsets of 5, i.e., for
each nonempty subset X we place a mark above the weight fj(X) in the histogram for f?;
one distinct mark is made for each such subset X.
The weight of any subset is in the range [1, NB]. Initialize, for each i, a pointer p? to 1
in the histogram for f?. The pointers Pt advance according to the following rules:
o+ If there are no marks on weight P2 in the histogram of f?, then advance p? to p? + 1.
o+ If there is exactly one mark on weight p? which corresponds to some subset X, remove
the marks corresponding to X from all the histograms and advance p? to p? + 1.
If more than one pointer can advance, we choose one among them arbitrarily, We
continue this process until the pointers cannot move any further. First we argue that not
all marks can be removed since every time a mark is removed, one of the pointers advances
and hence the potential function ? = --H1) always increases. Since each p? is bounded
by NB + I, ? is bounded by tNB. By assumption tNB <2N --H 3, and hence when the
pointers come to a halt there are at least two marks corresponding to nonempty subsets Xj1
and Xj2 on weight p? in the histogram of f?, for each i. The family ? = fXj1, Xi2I 1 < i <
has size at most 2t < Z and for each i, there are two nonempty minimum weight subsets,
X?1 and Xj2, of minimum weight p?, under the assignment f?.
Also when B = n0?1? and I = o(N/ log N), we can construct two sets which have the
same weight under all the assignments fi, f2...., ft. as follows. Since fi maps the nonempty
subsets of 5 to the range [1, NB], there exists a family A1 of nonempty subsets of 5, all of
which get the same weight under fi and such that IA1 I > 2NNB1. Similarly, there exists a
family A2 c A1 with IA2I > (2NNB)12, such that fj(X1) = f2(X2) VXi,X2 E A2, for i = 1,2.
Repeating this, we end up with a set At of nonempty subsets of 5 with lAt I > (2$Th". such
that the minimum weight element of At is not unique under none of fi. .2...., ft; since
2N?1			> 2 for I =			our clalm holds.			any scheme for Generalized isolation
--H			o(N/ log N),			Thus,
requires ?(log Z + log N) random bits. Theorem 1 also gives similar lower bounds when
the elements are assigned superpolynomial weights. In fact, we can prove the same lower
bound when the assignments map subsets of 5 to an arbitrary linearly ordered set of size
B since the above proofs use no property of the integers other than their total ordering.
3 Applications to Matching Problems
The Generalized isolating Lemma immediately yields randomness-efficient algorithms for
several problems related to matching. in this section, we only consider matchings in bi-
9
partite graphs; with more work, identical results can be obtained for matchings in general
graphs [19, 21]. The failure probabilities of all our algorithms can be made inverse polyno-
mial with only a constant blowup in the time and randomness complexities and a polynomial
blowup in the number of processors using two point sampling techniques of Chor & Gol-
dreich [5]. The new isolating lemma is a general tool to bound the randomness complexity
of a problem in terms of the number of its solutions. However, due to the large polyno-
mial weights used by our lemma, algorithms based directly on the lemma usually suffer a
processor penalty.
Notation We denote a bipartite graph G by G = (U,V?E), where U=?ui,u?,... ,un12?,
V =[vl,v2,.. . ,Vn/2?, and IF = m. The determinant of a matrix A is denoted by det(A).
The number of perfect matchings in G is denoted by IMat(G) I.
3.1 Algorithms for matching
To apply unique element isolation to perfect matching, we let the ground set be the set
of edges and let the family of subsets be the set of perfect matchings of G, as in [21]. By
the Generalized Isolating Lemma, given an upper bound Z on IMat(G)I, we can assign
polynomially bounded weights to the edges of C using O(log Z + log n) random bits such
that there is a unique perfect matching of minimum weight, with good probability. We
construct a matrix M[1..n/2, 1. .n/2] with
M[i,j] =			2wij			if (u1,v>) E E
0			otherwise
where Wij is the weight assigned to edge (uj, vj). A perfect matching in G can now be
found, if one exists, by inverting M via the NC2 algorithm of Csanky [6], as shown in
[21]. Note further that the additive O(log n) factor in the randomness complexity can be
absorbed by a processor penalty. For any graph G = (V,E), IMat(G)I < llvEV degree(v),
which is at most (2m/n)? since the sum of the degrees of the vertices is 2m. In the worst
case, by letting Z = (2m/n)? we obtain a randomness complexity of O(nlog(m/n)) which
improves the previous bound of O(m log n) [21]. Thus, we get
Theorem 2 There is an RNC2 aigorithm to find a perfect matching in a graph G (if one
exists) which uses O(log Z + logn) random bits, given an upper bound Z on IMat(G)j. In
the worst case, this algorithm uses O(n log(m/n)) random bits.
A careful analysis of the proof of our isolating scheme when applied to the worst case
where Z = (2m/n)? and m = 0(n2), shows that the following algorithm also achieves the
same randomness complexity: the edges of each vertex u E U are assigned weights pairwise
independentl? in the range [1, m7].
Perfect matching is a special case of the Exact Matching Problem: given a graph G
with edges colored red and blue arbitrarily and an integer k, an exact matching is a perfect
10
matching of G with exactly k red edges (Papadimitriou & Yannakakis [25]) Even though the
problem of finding an exact matching is not known to be in P, the Isolating Lemma has been
used to solve it in RNC2 [21]! By observing that isolation is needed only among the exact
matchings, we can link the randomness complexity of this problem to a bound X on the
number of exact matchings and not on the number of perfect matchings. Suppose we assign
a nonnegative integral weight Wij to every edge (u1, v>) E E. Let y be an indeterminate;
construct a symbolic matrix M?[1..n/2, 1..n/2] such that
Wj?
M?k,j] =			Wi>
0
if (ui,vj) E E and is colored red,
if (uj, v>) E E and is colored blue,
otherwise
Then, it is easy to see that the contribution to the coefficient of yk in det(M?) comes
precisely from the exact matchings in G and that if there is a unique minimum weight
exact matching M*, then its weight equals the highest power of 2, say p*, which divides
this coefficient of yk Eurthermore, any edge can be tested for membership in M* by
increasing its weight by 1 and testing if the new value of p* is higher than its old value or
not. Hence, this problem can be solved by using our Generalized Isolating Lemma over the
ground set E and the (unknown) family of exact matchings of G. Since the determinant of
a matrix in one variable can be computed in NC2 (Borodin, Cook & Pippenger [2]), we get
Theorem 3 Given an upper bound X on the number of exact matchings in a graph G, an
exact matching (if any) in G can be found in RNC2 using O(log X) random bits.
The Isolating Lemma has also been used to find the matching of largest cardinality in bi-
partite graphs by a reduction to the perfect matching problem. However the NC reductions
that have been used earlier [21, 19] do not suffice to get randomness--Hefficient solutions since
they cause a blow up in the number of solutions. Instead, we use the following reduction
from maximum matching to exact matching: Given a graph G = (V? E) we first construct
2 copies of G and color the edges in each of the copies red. Each vertex v in the first copy
of G is joined to vertex v in the second copy by a blue edge, to yield the resulting graph,
G1. If m is the size of the largest matching in G then it can easily be seen that there is an
exact matching with 2m red edges in G1, but no exact matching with more than 2m red
edges. Also, if Z is an upper bound on the number of maximum matchings in the graph G
the new graph has at most Z2 exact matchings with 2m red edges. Also note that if G is
bipartite then so is G1. Thus, for maximum matching, we first construct the new graph G'
and the new bound Z2, and run the above algorithm for exact matching, with each possible
value of m simultaneously in parallel using the same random bits. We output the matching
of largest cardinality that results in any of the parallel runs.
Theorem 4 There exists an RNC2 algorithm for maximum matching which uses O(log Z+
log n) random bits, where Z is a known bound on the number of maximum matchings in G.
11
3.2 Graphs with a polynomial number of perfect matchings
Grigoriev & Karpinski [11] consider the problem of finding all the perfect matchings in
graphs with a polynomial bound on the number of perfect matchings. Using techniques
from algebra, they give an NC2 algoritlim for this problem if the number of matchings
is bounded by ??gO.5?C n, and an NC3 algorithm when the bound is ?C for constant c.
Since their algorithm to extract a matching is limited by their procedure to detect if a
matching exists they suggest that l?gO.5?f n may be a limiting upper bound on the number
of matchings to find all (or even one) of the perfect matchings in NC2 via parallel algebra.
We present a NC2 algorithm for the detection problem which provides enough information
to find all matchings in NC2 even when the number of matchings is polynomially bounded.
Besides the improvement in running time, our algorithm is considerably simpler than the
algorithm of Crigoriev & Karpinski.
As before, we let S and ? be E and Mat(G) respectively. Running steps 1 and 2
of the generalized Isolating scheme, we use O(log n) random bits to assign each edge a
polynomially bounded weight such that all the perfect matchings of 0 have distinct weights
with probability at least 1/2. Let Wi,> be the weight assigned to edge (uj, v>). Construct a
matrix A with
A[i,j] = 22xw,? if (ut.,v>) ? E
0			otherwise
Since every matching has a distinct weight, det(A) gives information about every perfect
matching as shown below.
Assume that step 2 succeeds i. e. all the perfect matchings indeed get distinct weights.
If we denote the matrix obtalned from M by removing its ith row and jth column by Mi>,
then by definition
(M?')\j,i1 = (?1)t+>det(Mi>)
det(M)
Now, if there is a perfect matching of weight k contalning the edge (uj, v>), then det(Mi>)
is of the form
k--H1
+22X(k?wij) + Z ae22?(??wij) + ? ae22x(??wij),
e>--Hk+1
where each a' is in f--H1,o,1?. Since
this is of the form
k--H1
I ? ae22x(e?wij)I < 22X(k?wij)?1
e=0
+22X(k?ivij) ? ?? ? 22(k?wij+1) + ? 22(k?wi,)?1
12
where flo is a nonnegative integer and 0 <x < 1. Similarly, if there is no perfect matching
of weight k containing the edge (ut, vj), then det(M,?) is of the form
+?? ? 22(k?ivij+1) + ? ? 22(k?ivi?)?1
Hence, there is a perfect matching of weight k containing the edge (uj, v>) if and only if
J(M?1)[j,i] det(M) . 22wijI (mod 22(k?1))
is of the form 4ni + ?, where fli is an integer and ? = 1 or 2. ff there is no matching of
weight k then y = 0 or 3. Since k is polynomially bounded we can extract all matchings.
Also, since we use O(log Z + log n) = O(log n) random bits, we can derandomize this by
searching over all points in the sample space in parallel to get
Theorem 5 There is an NC2 algorithm to detect if a perfect matching exists and to find
all perfect matchings in a graph G, when given that IMat(G) < nc for some constant c.
We can obtain the same result for exact matching and maximum matching problems given a
polynomial bound on the number of exact matchings and maximum matchings respectively.
Grigoriev & Karpinski also give a Las Vegas RNC3 algorithm for the problem of testing
if a graph has at most nc perfect matchings, which uses expected O(n2c+8.5 log n) random
bits. We can, using the algorithm of Theorem 5 and by extending ideas of [17, 13], improve
on the running time and substantially on the number of random bits used, as follows:
Karloff[13] presents an NC2 algorithm which calls a perfect matching algorithm (oracle)
on n + 1 graphs (each with n --H 1 or n vertices and at most m edges) in parallel, and
which, assuming that these calls worked correctly, will announce correctl? if G has a perfect
matching. or not; in any case, if it ever says that IMat(G)I = 0, then the number of perfect
matchings is indeed zero. Actually, Karloff's result is more general --H it works for maximum
matchings. Note that in conjunction with any Monte Carlo RNC2 aigorithm to find a
perfect matching (in particular, ours) this yields a Las Vegas RNC2 algorithm to decide
if G has a perfect matching or not, and if so, to produce one. We first make the error
probability of our perfect matching algorithm at most 2(ni+1) (as mentioned in Section 2,
this can be done in RNC2) and using only O(nlog(m/n)) random bits then invoke Karloff's
algorithm, which will make calls in parallel to our algorithm, using the same sequence of
random bits for each call; the probability that at least one of these calls produced a wrong
result is at most 2(?n%\) = 1/2. Hence, we can decide if JMat(G) > 0 or not correctly, using
an expected O(n log(m/n)) many random bits. The above probability can be made any
inverse polynomial with a processor penalty using the techniques of two--Hpoint sampling[5]
If we conclude that IMat(G) I > 0, then we run the algorithm of Section 3.2 to generate
all the perfect matchings of G, assuming that JMat(G) I < nc + 1. Kozen, Vazirani and
Vazirani[17] give a simple NC2 algorithm to test given a perfect matching whether there
13
are other perfect matchings in the graph. A direct extension of the technique yields a
NC2 procedure to check given a polynomial number of perfect matchings whether there
are other perfect matchings. The Las Vegas algorithm will then check if there are other
perfect matchings in the graph besides the ones generated and accept if there are other
matchings, otherwise it reports a failure. If G has at most nC perfect matchings, then at
most nC perfect matchings will be generated and we will pass the test for other matchings
and so the algorithm accepts correctly with high probability.
Theorem 6 There exists a Las Vegas RNC2 algorithm to test if a given graph G has
IMat(G)I < nC whose expected randomness complexity is O(nlog(m/n)).
3.3 Randomness-Efficient algorithms with no information on IMat(G)I
The algorithms of Theorem 2 can be used to obtain randomness--Hefficient algorithms for
perfect matching even when no upper bound on the number of perfect matchings is given,
by using the worst case upper bound of Z = (2m/n)?. However, the following algorithm
gives a much better randomness complexity:
for i 0 to [log2log2((2m/n)fl)? do
Let Z --H 22' and run the algorithm of Section 3.1 to find a perfect matching;
exit if a perfect matching is found.
If there is at least one perfect matching, then this algorithm will find a perfect matching with
good probability when 22? > IMat(G)I. If M is the number of perfect matchings then the
number of random bits used and the time taken will be O(log M) and O(log2 n log log M)
respectively with good probability, and so we get
Theorem 7 Let M=IMat(G)I. There is an RNC algorithm to find a perfect matching in
G with no given upper bound on M, which uses O(log M) random bits and runs in time
O(log2 n log log M) = O(log3 n) with high probability, if M > 0; in the worst case, it uses
O(nlog(m/n)) random bits and O(log3 n) time.
4 Other applications
The Isolating Lemma is a very abstract and powerful tool to make one solution from a
possibly exponential sized collection stand out. Due to its general nature it has several
applications. Thus, our generalized Isolating Lemma leads to randomness--Hefficient solutions
to various problems, which we describe in this section.
14
4.1 Randomized reductions from SAT to USAT
An important result in complexity theory is the random reduction, due to Valiant & Vazi-
rani, from languages in NP to USAT, the language of uniquely satisfiable Boolean formulae
[32]. This reduction is at the core of several fundamental results in complexity theory, most
notably in the results of Toda on the unexpected power of counting classes [29]. The Iso-
lating Lemma has been used to derive an alternative random reduction in [21]. We apply
the Isolating Lemma to get a slightly different reduction and here, our generalization yields
better randomness complexity.
Given a formula F(xi,x2,... , xn) as input, to use the isolating lemma we let the ground
set 5 be the set of variables ?x1,x2,... , xn? and let the family ? be the satisfying assign-
ments of F, where a satisfying assignment is represented by the subset of variables that
are true in it. Assign weights w1...., w1L to the ground set elements as prescribed by the
generalized isolating lemma and choose a random element y in the range [1,n5]. Consider
the following reduction:
On input F(xi,. ..,x?),wi,. . .,Wn,U we construct an NP machine M which works
as follows: Guess an assignment for the variables x1...., X?. If the assignment satisfies
the formula F and the weight of the assignment under the weight assignment w1... . ,
is equal to ? then we accept. Notice that since the weight assignment scheme succeeds
with probability 2?' if F is satisfiable then with probability ?21 there is one minimum weight
satisfying assignment. Since all the assignments have a weight in the range [1, n8] and y is
chosen uniformly at random from [1, n8] we have
F is satsfiable Prob[ M accepts on exactly one path] > 2 1
x n5
If F is not satisfiable then the machine M clearly accepts on no paths. Given this machine
M we can construct using the Cook--HLevin reduction a boolean formula F' which has exactly
the same number of satisfying assignments as the number of accepting paths of M. So the
random reduction first assigns weights to the variables, chooses a random weight y and then
constructs the formula F' described above. By the description above it is easy to see that
F is satisfiable ? Prob[ F'is uniquely satisfiable] >
2 >c n5
F is not satisfiable			Prob[ F' is not satisfiable] = 1
This reduction requires O(log Z + log n) random bits, where Z an upper bound on the
number of satisfying assignments of F. In the worst case this randomness complexity is
0(n), which improves on the O(nlogn) bound of [21], the 0(n2) bound of [32] and matches
the result of Tami [26]. Thus we obtain:
Theorem 8 There is a randomized redttction from SAT to USAT which uses O(log Z +
log n) random bits, where n and Z are the number of variabies and an upper bound on the
number of satisfying assignments respectively.
15
If the number of satisfying assignments of F is polynomially bounded, as in case of languages
in the class FewP, the reduction uses O(log n) random bits, This can be derandomized to
yield new proofs of the results FewP C ?P [3] and FewP C ?P [16] as described below.
Definition A language L is in the class FewP if there is a nondeterministic polynomial
time machine M which accepts L and a polynomial q such that for all strings x, M (x)
accepts on at most q(IxI) paths.
Note that for a language L in FewP, given a string x, the Cook--HLevin reduction produces
a formula F with at most a polynomial number of satisfying assignments such that x is in
L iff F is satisfiable.
Definition A language L is in the class ?P if there is a nondeterministic polynomial time
machine M such that x is in L iff M on input x accepts on an odd number of paths.
The class was first defined by Papadimitriou and Zachos[24] who also show that the class
is closed under many operation: in fact, p?P --H ?P. When we derandomize the above
reduction for languages in FewP, we can get a polynomial number of formulas such that
F is satisfiable iff one of these formulas is uniquely satisfiable. Also, if F is unsatisfiable
then none of these formulas is satisfiable. Since the condition in the antecedents can easily
be checked in p?P we can get a new proof of the result that FewP C ?P.
Definition A language L is in the class &P iff there is a nondeterministic polynomial
time machine M and a polynomial time computable function f such that x is in L iff M
on input ? accepts on exactly f(x) paths.
We can use ? P to test if one of a polynomial number of formulas has exactly one satisfying
assignments as follows: Let F1, ..., Ft be formulas on n variables each, with Si, ..., St
satisfying assignments respectively. If we could construct a formula F' with (si ...... (5t --H
1) satisfying assignments then F' would have exactly 0 satisfying assignments iff one of the
Fj5 has exactly one satisfying assignment. However doing this directly involves constructing
formulas with one less satisfying assignment than the Fj5 which is highly intractable[23].
We do this slightly indirectly as follows: Each term in the product (si --H 1)... (st --H 1)
is of the form +8j1 Sj2 ... Sj where r < t. We can easily construct a formula which has
8j1 Sj2 ... ?ir satisfying assignments and so if the coefficient of this term is +1 then we are
done. However if the coefficient is --H 1 then we construct a formula with 2p(n) --H Sj? 8j2 ... ?ir
satisfying assignments, where p(n) = t X n. A nondeterministic polynomial time machine
M which accomplishes this works as follows: First, M nondeterministically chooses a term
in the product (si --H 1)... (st --H 1). If the term is of the form 8j1Sj2?? Sj it guesses r
assignments and accepts iff the assignments satisfy F?1... . , Fi respectively. If the term is
of the form --H1 x 8i1 ..... Sj?? it guesses t assignments and accepts iff the first r formulas
do not satisfy ....... , F\ or the last t --H r assignments are all zeros. It can be easily
16
verified that if the term has coefficient 1 then M accepts on 5j15j2?? 5j paths and if the
coefficient is --H1 then M accepts on 2p(n) ?5j15j2?? 5j paths. Since the number of terms
with coefficient --H1 is 2?--H?, M accepts on (si ...... (8t --H 1) + 2???? x 2?--H? paths. Using
the Cook--HLevin reduction one can construct a formula G with exactly the same number of
satisfying assignments. Now G has exactly 2???? x 2?--H? satisfying assignments iff one of the
original formulas has exactly one satisfying assignments. Thus the reduction also gives a
new proof of FewP C ?P.
Here again we wish to emphasize that though there are many proofs of the above two
results, our proofs follow directly from bounding the randomness complexity of the general
randomized reduction.
4.2 Improved parallel randomness complexity for problems on matroids
The Isolating Lemma has been used to obtain RNC algorithms for basic problems on
linearly representable matroids such as matroid intersection and matching (Narayanan,
Saran & Vazirani [22]). These problems are generalizations of bipartite and general graph
matching.
Definition A set system M = (s, ?) is a matroid if:
o+ ? E ?,
o+ if A c B C S and B E ?, then A E ?, and
o+ ifAiE?andA?E?wfthIA2I=IAiI+1,thenthereexistsxEA2--HAisuchthat
A1 u ?x) E ?.
Every element of ? is called an independent set. A basic consequence of the matroid
axioms is that every maximal independent set is also a maximum independent set, and
the cardinality of any maximum independent set of M is also called the rank of M. A
matroid M of rank r over a ground set S of cardinality n is h'near1? representabie over a
field F if there exists a matrix C E F??? whose columns are indexed by the elements of
S, such that a subset of S is independent in M iff the corresponding set of columns of C
are linearly independent over F. M is 1inear1? represented if it is presented as the matrix
B. Henceforth, the field F is assumed to be the field of rationals, Q. All the results of [22]
and of this section hold oniy for linearly represented matroids. For a good introduction
to the theory of matroids see Welsh[34]. For other work on randomized algorithms for the
matroid problem see Camerini, Galbliati and Maffioli[4].
The matroid intersection problem is to find a maximum cardinality independent set in
both of two given matroids M1 and M2, each of rank r and over the same ground set S of
cardinality n. In this case, we observe that the size of the family on which the Isolating
Lemma operates, as presented in [22], is at most I x ((r?r?))2 x (r --H h)! where h is the
17
size of the largest set in M1 n M2 and I is the number of sets of size h in M1 n M2.
Since this can be bounded by (nr2)h x r! < (nr2)r x rr < n4r, we can use generalized
isolation to reduce the randomness complexity from the previous bound of O((n+ r2) log n)
[22] to O(r log n), improving by a factor of at least ?($)n in all cases, and by more in
general. If h > r --H O(logr n) and there is a polynomial (in n) bound on I then since
1((r?r?))2 x (r --H h)! --H n0('), we get the first NC algorithms. In the case of bipartite
matching which is a special case of matroid intersection, h = r, and a polynomial bound
on I corresponds exactly to a polynomial bound on the number of matchings in the input
graph. Thus, this gives one way to generalize the results of [11] to matroids.
Theorem 9 Matroid intersection for linearl? represented matroids of rank r can be solved
in RNC2 using O(r log n) random bits. If the cardinality of the maximum intersection is
given to be at least r --H O(log? n), and if the number of maximum cardinaht? intersections
is given to be bounded b? a given pol?nomial of n, then it can be solved in NC2.
For linearly represented vectors, the matroid matching problem is the following: given m
pairs of vectors over Q2fl, pick the largest number of pairs so that the vectors picked are
linearly independent. For this problem, the RNC2 algorithm of ([22], Theorem 4.3) uses
the Isolating Lemma on a set family over a ground set of m + (22fl) elements and at most
m+?(22fl) <(m+2n2)?
subsets and thus by invoking the Generalized Isolating Lemma, we improve the randomness
complexity from O((m+n2)log(m+n2)) [22] to O(nlog(m+n2)). We can count the size
of the size of the family, to which the Isolating Lemma is applied to in, more carefully to
bound the randomness complexity of the algorithm to be O(log(I X (2n2%h) x (2n --H
where h is the maximum number of pairs that can be picked so that the union is linearly
independent and I is the number of ways these h pairs can be picked. As in the case
of matroid intersection we can obtain deterministic algorithms if I is polynomial and if
h > n --H log? m. Tiwari, using sparse interpolation techniques, gives NC algorithms for this
problem when the number of full dimensional solutions (i. e., when h = n) is given to be
polynomially bounded in n and m [28]. Thus, our result yields a generalization.
Theorem 10 Matroid matching can be solved in RNC2 using O(nlog(m + n2)) random
bits. If h > n --H log? m, is the size of the largest number of pairs whose union is linearly
independent and there is a polynomial bound on the number of ways such a set of h pairs
can be picked, matroid matching can be solved in NC2
18
5 Conclusions and open problems
The main contribution of this work is our Generalized Isolating Lemma. For various prob-
lems solvable via randomness in general [21, 22, 32] and deterministically when the number
of solutions is small [17, 11, 3], this lemma bounds their randomness complexity in terms of
the number of solutions. Our results span the spectrum of the number of solutions, imply,
and sometimes improve the previously known results at the extremes. On the other hand,
our lower bound for isolation implies that attempts to solve these problems deterministi-
cally based on isolation must also exploit their structure, rather than view them merely as
abstract unknown collections of sets.
A direct open problem falling out of the Generalized Isolating Lemma is to reduce the
magnitude of the weights assigned by it to the elements of the ground set; currently, they
can be as high as N7. In the context of matching, this will lead to more processor--Hefficient
RNC algorithms. For the random reduction a decrease in the magnitude of the weights of
the elements will increase the success probability of the reduction.
The lower bound for isolation that we prove holds only for schemes which work oblivious
of the family of solutions that it is tring to isolate one solution from. An interesting question
that arises here is: can we use some knowledge of the structure of the solution space that
we are trying to isolate one solution from to reduce the randomness complexity of isolation
or even perhaps obtain deterministic algorithms? In case of the perfect matching problem
it would be interesting to see if we can obtain deterministic algorithms for special classes
of graphs with this framework.
Acknowledgments
We would like to thank our advisors Juris Hartmanis and David Shmoys for their guidance,
suggestions and support. This paper has benefited greatly from discussions with several
other people too. We are particularly indebted to Joseph Cheriyan, Steve Mitchell, Moni
Naor, Eva Tardos and Vijay Vazirani. A preliminary version of this paper was presented at
the 25th Annual Symposium on the Theory of Computing. We would like to thank Martin
Tompa for making valuable comments on the conference proceedings version of this paper.
References
[1] L. Adleman. Two theorems on random polynomial time. In Proc. IEEE Symposium
on Foundations of Computer Science, pages 75--H83, 1978.
[2] A. Borodin, 5. A. Cook, and N. Pippenger. Parallel computation for well--Hendowed
rings and space--Hbounded probabilistic machines. Information and Controt, 58:113--H
136, 1983.
19
[3] J-Y. Cai and L. Hemachandra. On the Power of Parity Polynomial Time. Mathematical
S?stems Theor? 23(2):95--H106, 1990.
[4] P. M. Camerini, G. Galbiati, and F. Maifioli. Random pseudopolynomial algoritlims
for exact matroid problems. Journal of Algorithms, 13(2):258--H273, 1992.
[5] B. Chor and O. Goidreich. On the power of two--Hpoint sampling. Journal of Complexity,
5:96--H106, 1989.
[6] L. Csanky. Fast parallel matrix inversion algoritlims. SlAM J. Comput., 5:618--H623,
1976.
[7] E. Dahihaus and M. Karpinski. The matching problem for strongly chordal graphs is
in NC. Technical Report 855--HCS, University of Bonn, 1986.
[8] N. de Bruijn. On the number of positive integers < x and free of prime factors > y.
Proc. Kon. Ned. Akad. Wet. (Indag. Math. 13), A54:50--H60, 1951.
[9] A. V. Goldberg, 5. A. Plotkin, D. B. Shmoys, and E. Tardos. Using interior--Hpoint
methods for fast parallel algorithms for bipartite matching and related problems. SlAM
J. Comput., 21(1):140--H150, 1992.
[10] A. V. Goldberg, 5. A. Plotkin, and P. M. Vaidya. Sublinear--Htime parallel algorithms
for matching and related problems. Journal of Algorithms, 14(2):180--H213, 1993.
[11] D. Yu. Grigoriev and M. Karpinski. The matching problem for bipartite graphs with
polynomially bounded permanents is in NC. In Proc. IEEE Symposium on Foun-
dations of Computer Science, pages 166--H172, 1987. See also D. Yu. Grigoriev, M.
Karpinski and M. F. Singer, Fast parallel algorithms for multivariate polynomial in-
terpolation over finite fields, SlAM J. Comput., Vol. 19, 1990, 1059--H1063.
[12] L. K. Grover. Fast parallel algorithms for bipartite matching. In Proceedings of the In-
teger Programming and Combinatorial Optimization Conference, pages 367--H384, 1992.
[13] H. J. Karloff. A Las Vegas RNC algorithm for maximum matching. Combinatorica,
6(4):387--H391, 1986.
[14] R. M. Karp, E. Upfal, and A. Wigderson. Constructing a perfect matching is in
Random NC. Combinatorica, 6(1):35--H48, 1986.
[15] P. W. Kastelyn. Graph theory and crystal physics. In F. Harary, editor, Graph Theory
and Theoretical Physics, pages 43--H110. Academic Press, New York, 1967.
20
[16] J. K5bler, U. Sch5ning, 5. Toda, and J. Toran. Thring machines with few accepting
computations and low sets for PP. Journal of Computer and System Sciences, 44:272--H
286, 1992.
[17] D. Kozen, U. V. Vazirani, and V. V. Vazirani. NC algorithms for comparability graphs,
interval graphs, and testing for unique perfect matching. In Proceedings, FST & TCS
Conference, Lecture Notes in Computer Science # 206, pages 496--H503. Springer-Verlag,
Berlin, 1985.
[18]
C. H. C. Little. An extension of Kastelyn's method of enumerating the 1--Hfactors
of planar graphs. In D. Holton, editor, Combinatorial Mathematics, Proc. Second
Australian Conference, pages 63--H72. Lecture Notes in Mathematics 403, Springer--H
Verlag, Berlin, 1974.
[19] L. Lova'sz and M. Plummer. Matching Theory. North--HHolland, Amsterdam, 1986.
[20] G. L. Miller and J. Naor. Flow in planar graphs with multiple sources and sinks. In
Proc. IEEE Symposium on Foundations of Computer Science, pages 112--H117, 1989.
[21] K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Matching is as easy as matrix
inversion. Combinatorica, 7(1) :105--H113, 1987.
[22] H. Narayanan, II. Saran, and V. V. Vazirani. Randomized parallel algorithms for
matroid union and intersection, with applications to arborescences and edge--Hdisjoint
spanning trees. In Proc. ACM/SIAM Symposium on Discrete Algorithms, pages 357--H
366, 1992.
[23]
[24]
M. Ogiwara and L. Hemachandra. A Complexity theory for feasible closure properties.
In Proceedings of the Sixth Annual Conference on Structure in Complexity Theory,
pages 16--H27, 1991.
C. Papadimitriou and 5. Zachos. Two Remarks on the Power of Counting. In Proc. 6th
GI Conference on Theoretical Computer Science,. Lecture Notes in Computer Science
Springer-Verlag, #1?5, pages 276--H296, 1983.
[25] C. H. Papadimitriou and M. Yannakakis. The complexity of restricted spanning tree
problems. J. Assoc. Comput. Mach., 29(2):285--H309, 1982.
[26] J. Tarni. Randomized polynomials, Threshold circuits and the Polynomial hierarchy.
In Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in
Computer Science #480, pages 238--H250,1991.
[27] W. Thrash. A note on the least common multiples of dense sets of integers. Technical
Report #93-02-04, Department of Computer Science & Engineering, University of
Washington, Seattle, February 1993.
21
[28]
P. Tiwari. Parallel algorithms for instances of linear matroid parity with small number
of solutions. Technical Report RC 12766, IBM T.J.Watson Research Center, May
1987.
[29] 5. Toda. PP is as hard as the Polynomial-time Hierarchy. SlAM J. Comput., 20(5):865-
877, 1991.
[30] M. Tompa. Lecture notes on probabilistic algorithms and pseudorandom generators.
Technical Report #91-07-05, Department of Computer Science & Engineering, Uni-
versity of Washington, Seattle, July 1991.
[31] P. M. Vaidya. Reducing the parallel complexity of certain linear programming prob-
lems. In Proc. lEEF S?mposium on Foundations of Computer Science, pages 583--H589,
1990.
[32] L. 0. Valiant and V. V. Vazirani. NP is as easy as detecting unique solutions. Theo-
reticat Computer Science, 47(1):85--H93, 1986.
[33] V. V. Vazirani. NC algorithms for computing the number of perfect matchings in
K3,3--Hfree graphs and related problems. Information and Computation, 80:152--H164,
1989.
[34] D. J. A. Welsh. Matroid Theory. Academic Press, New York, 1976.
22
