For a family of sets $F \subseteq 2^U$,
we consider a weight function $w:U\to\R$,
naturally extended to subsets of $U$
by $w(S) = \sum_{e\in S}w(e)$.
A weight function is said to be **isolating for $F$**
if it assigns a minimum value to a unique set
(i.e., exists $S\in F$ such that for every $S'\in F$
if $w(S') \leq W(S)$ then $S'=S$).

We seek to construct a weight function with range $[poly(|U|)]$ that is isolating for all families $F$, but that's impossible. It is also impossible to have $N = poly(|U|)$ such weights functions such that for each family at least one of these weight functions is isolating. So we restrict the class of families.

They associate aech family $F$ with a polytope $P(F)$
by associating each $S\in F$ with its indicator vector,
denoted $v_S\in\GF(2)^{|U|}$ (such that $v_S(e)=1$ iff $e\in S$),
and take the convex hull of all vectors associated with
the sets in $F$. Hence, finding an isolating weight amounts
to finding a weight that obtains its minimum on a single point
in the polytope. Since each weight function obtains its minimum
on a face of the polytope, we gradually augment the weight
functions such that the *quality* of this face is increased,
where the quality of a face is the length of (Boolean) vectors
that are not parallel to this face.
Specifically, in each step, we select a small set of weights
such that the quality is doubled, and so we are done in
logarithmically many steps.
The weights are combined by taking the cartesian product
(e.g., weights $w$ and $w'$ are combined to $(N+1)w+w'$).

The key property is one that guaranteed that we can double quality by using a small set of weights. In the case of the Perfect Matching polytopes (for bipartite graphs) this reduces to claiming that an $n$-vertex graph that has no cycles of length at most $t$ has at most $n^4$ cycles of length at most $2t$. (To see this, map each cycle of length at most $2t$ to a 4-tuple of vertices that reside in distance at most $r/2$ on this cycle, and note that this mapping is 1-1 or else a short cycle is formed.)

We present a geometric approach towards derandomizing the Isolation lemma for a given family, i.e., deterministically constructing a weight assingnment which ensures a unique minimum weight set in the family. The idea is to work with a polytope corresponding to the family of sets. In this talk, we present the approach in terms of general polytopes and describe a sufficient condition on the polytope for this approach to work. The approach gives a quasi-polynomially bounded weight assignment. Finally, we show that two specific families - perfect matchings in bipartite graphs and common base sets of two matroids - satisfy the required condition and thus, we get an isolating weight assignment for these cases. This also puts the two problems in quasi-NC.

Back to list of Oded's choices.