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.