<p><em>(First of all, sorry for the long article which makes you want to skip through, but since the background and motivations are important to this question or it would be nonsense to the main problem, forgive me if this makes you sleep. I owe you a cup of coffee.)</em></p>

<h2>Background</h2>

<p><strong><a href="http://en.wikipedia.org/wiki/Isolation_lemma" rel="nofollow">Isolation lemma</a></strong>, one of the best tool in complexity theory invented by K. Mulmuley, U. Vazirani and V. Vazirani in "<a href="http://www.cs.berkeley.edu/~vazirani/pubs/matching.pdf" rel="nofollow">Matching is as easy as matrix inversion</a>", have been used to prove many amazing results like an RNC-algorithm for matching in the above paper; <a href="http://en.wikipedia.org/wiki/Valiant-Vazirani_theorem" rel="nofollow">Valiant–Vazirani theorem</a> which is a randomized reduction from NP problems to USAT; <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.2546&amp;rep=rep1&amp;type=pdf" rel="nofollow">NL/poly=UL/poly</a>; and many others. <a href="http://www.cs.rochester.edu/~lane/=companion/isolation.pdf" rel="nofollow">Surveys</a> and <a href="http://rjlipton.wordpress.com/2009/07/01/the-isolation-lemma-and-beyond/" rel="nofollow">introduction in blogs</a> are also all over the web. </p>

<p>In the center of the isolation lemma, we use randomization to assign weights on the base set $U$, such that for a family $\mathcal{F}$ of subsets of $U$, there is a unique minimum weighted subset in $F$ with high probability. Formally,</p>

<blockquote>
  <p><strong>Lemma.</strong> Let $U$ be a set of size $n$, and $\mathcal{F}$ be a non-empty family containing elements which are the subsets of $U$. Uniform-randomly assign integral weights in $[2n]$ on the set $U$, then there exist a unique minimum weighted subset in $\mathcal{F}$ with probability at least $1/2$.</p>
</blockquote>

<p>A stronger form which covers a collection of $\mathcal{F_1}, \ldots, \mathcal{F_m}$ that is used in practical situations can be found in the <a href="http://www.cs.rochester.edu/~lane/=companion/isolation.pdf" rel="nofollow">survey</a>. There are also some variants that may reduced the use of random bits, or derandomized the lemma to get a deterministic weight assigning algorithm when the size of $\mathcal{F}$ is not too large.</p>

<h2>Problem</h2>

<p>After a search of literature, it seems that all the research on this topic were all focus on isolating a <em>unique</em> subset of $U$. I want to know whether there is any obvious reason that we don't have a <em>weak</em> isolation lemma, in the sense that the number of minimum weighted subsets is bounded by a particular bound, and the requirement for the weak lemma is less than the original one. For example, do we have a lemma that only isolates $O(\log n)$ minimum weighted subsets? How about linear or polynomial? Since the size of $\mathcal{F}$ is at most $2^n$, when the bound is set to $2^n$, the result becomes trivial since no isolation is needed.</p>

<blockquote>
  <p><strong>Problem.</strong> Is there any research on the notion of <em>weak</em> isolation, that only limits the number of minimum weighted subsets instead of a unique one? If so, is there any references? If not, what is the most obvious obstacle toward such a result?</p>
</blockquote>

<p>I've been trying to prove such a lemma with some approaches, but despite of using the exactly same techniques (thus the same requirements) which is clearly no better than the original one (since with the same requirements you can indeed isolate a unique subset), there is no success to reduce any conditions we need, even in the case that we only need a loose bound on the number of minimum subsets, say polynomial. </p>

<p><em>(please read on if you need motivations to the problem! The part below contains some technical details to the usage of the lemma, and some applications to log-space computations.)</em></p>

<hr>

<h2>Motivation</h2>

<p>I am working on the problems in log-space computations, precisely the relation between classes $\mathsf{NL}$, $\mathsf{UL}$, and many other classes below and in between.
Consider the above lemma, which requires $O(n \log n)$ random bits if we assign weights to $U$ accordingly. A random-bit-saving version of the lemma is presented in <a href="http://portal.acm.org/citation.cfm?id=167213" rel="nofollow">this paper</a> by Chari et al., which states:</p>

<blockquote>
  <p><strong>Lemma.</strong> Let $U$ be a set of size $n$, and $\mathcal{F}$ be a non-empty family containing elements which are the subsets of $U$. There is a way of assigning weights in $[n^7]$ on $U$ with $O(\log|F|+\log n)$ random bits, such that there exist a unique minimum weighted subset in $\mathcal{F}$ with probability at least $1/4$.</p>
</blockquote>

<p>That gives us an $\mathsf{USPACE}[O(\log|F|+\log n)]$ algorithm for reachability. Of course this is a pity bound, since by <a href="http://en.wikipedia.org/wiki/Savitch%27s_theorem" rel="nofollow">Savitch's theorem</a> we have $\mathsf{NL} \subseteq \mathsf{L}^2 \subseteq \mathsf{UL}^2$.</p>

<p>But what if we consider the reachability problem with a restriction that there are at most $f(n)$ paths from the source to any node in the graph? This defines the problem $\mathtt{Reach}[f(n)]$, and we have $\mathtt{Reach}[2^n]$ to be the normal reachability problem. By setting $f(n)$ a polynomial, applying the above lemma together with an $\mathsf{UL}$-algorithm for reachability in graphs with a minimum unique path (see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.2546&amp;rep=rep1&amp;type=pdf" rel="nofollow">the paper</a> for more details), we can solve $\mathtt{Reach}[n^{O(1)}]$ in $\mathsf{UL}$. (The result occurs in <a href="http://cse.unl.edu/~rtewari/unamb.pdf" rel="nofollow">this recent paper</a>. In fact they use a stronger version of the lemma, which isolates every paths in the graph by a constructive way.)</p>

<p>If a weaker isolation lemma is known to have less restrictions on either the size of $\mathcal{F}$, or the number of random bits being used, we can provide better bounds on the problem $\mathtt{Reach}[f(n)]$, with the help of some modifications to solve reachability in graphs with few minimum paths. Hopefully if the lemma is <em>weak</em> enough to set $f(n) = 2^n$, and we can obtain some better bounds about the important class $\mathsf{NL}$.</p>

<p>Any comments on the proof techniques or obstacles will give insight to the question, and I would like to know that whether this idea has a tiny little chance of success, or it is just a completely impossible concept.</p>

CC BY-SA 2.5
2010-12-10T18:58:19.023Z
This is an interesting variant.  If you limit the number to $\operatorname{poly}(n)$, then you would likely be placing NL in FewL (non-deterministic log-space with at most a polynomial number of accepting paths).
Derrick Stolee
CC BY-SA 2.5
2010-12-10T19:13:45.380Z
@Derrick: That is pretty much the motivation of this question. :) But that will need some additional criteria, say the number of random bits being used should be $O(\log n)$, and we can not pose any constrain on the size of *F*. Still some weaker results may be obtained if we have further insights to this variant. Any idea?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-10T19:54:58.683Z
I am unsure that even with $O(\log n)$ random bits that the isolation can be derandomized, since the resulting weight function would need to be deterministically verified to be min-unique, which is hard.
Derrick Stolee
CC BY-SA 2.5
2010-12-10T20:10:50.107Z
Maybe verify the min-uniqueness (min-fewness?) deterministically is too strict, some variant of inductive counting technique which runs in FewL may do the job, just like the one in the result NL/poly = UL/poly.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-11T06:08:26.160Z
Would you please explain why this "weak isolation lemma" is useful?
Dai Le
CC BY-SA 2.5
2010-12-11T06:20:15.287Z
@Dai Le: Sure, since there are some direct applications to the weak lemma, and maybe the current version of the article is not well-written, I'll revise the entire question to make it both more attractive and self-contained.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-11T06:26:31.630Z
That would be great!
Dai Le
<cc.complexity-theory><randomness>
Is there any research on the notion of weak isolation?
Hsien-Chih Chang 張顯之
# Is there any research on the notion of weak isolation?

(Asked by: username_0 on 2010-12-10)

*(First of all, sorry for the long article which makes you want to skip through, but since the background and motivations are important to this question or it would be nonsense to the main problem, forgive me if this makes you sleep. I owe you a cup of coffee.)*

## Background

**[Isolation lemma](http://en.wikipedia.org/wiki/Isolation_lemma)**, one of the best tool in complexity theory invented by K. Mulmuley, U. Vazirani and V. Vazirani in "[Matching is as easy as matrix inversion](http://www.cs.berkeley.edu/~vazirani/pubs/matching.pdf)", have been used to prove many amazing results like an RNC-algorithm for matching in the above paper; [Valiant–Vazirani theorem](http://en.wikipedia.org/wiki/Valiant-Vazirani_theorem) which is a randomized reduction from NP problems to USAT; [NL/poly=UL/poly](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.2546&rep=rep1&type=pdf); and many others. [Surveys](http://www.cs.rochester.edu/~lane/=companion/isolation.pdf) and [introduction in blogs](http://rjlipton.wordpress.com/2009/07/01/the-isolation-lemma-and-beyond/) are also all over the web.

In the center of the isolation lemma, we use randomization to assign weights on the base set $U$, such that for a family $\mathcal{F}$ of subsets of $U$, there is a unique minimum weighted subset in $F$ with high probability. Formally,

> **Lemma.** Let $U$ be a set of size $n$, and $\mathcal{F}$ be a non-empty family containing elements which are the subsets of $U$. Uniform-randomly assign integral weights in $[2n]$ on the set $U$, then there exist a unique minimum weighted subset in $\mathcal{F}$ with probability at least $1/2$.

A stronger form which covers a collection of $\mathcal{F\_1}, \ldots, \mathcal{F\_m}$ that is used in practical situations can be found in the [survey](http://www.cs.rochester.edu/~lane/=companion/isolation.pdf). There are also some variants that may reduced the use of random bits, or derandomized the lemma to get a deterministic weight assigning algorithm when the size of $\mathcal{F}$ is not too large.

## Problem

After a search of literature, it seems that all the research on this topic were all focus on isolating a *unique* subset of $U$. I want to know whether there is any obvious reason that we don't have a *weak* isolation lemma, in the sense that the number of minimum weighted subsets is bounded by a particular bound, and the requirement for the weak lemma is less than the original one. For example, do we have a lemma that only isolates $O(\log n)$ minimum weighted subsets? How about linear or polynomial? Since the size of $\mathcal{F}$ is at most $2^n$, when the bound is set to $2^n$, the result becomes trivial since no isolation is needed.

> **Problem.** Is there any research on the notion of *weak* isolation, that only limits the number of minimum weighted subsets instead of a unique one? If so, is there any references? If not, what is the most obvious obstacle toward such a result?

I've been trying to prove such a lemma with some approaches, but despite of using the exactly same techniques (thus the same requirements) which is clearly no better than the original one (since with the same requirements you can indeed isolate a unique subset), there is no success to reduce any conditions we need, even in the case that we only need a loose bound on the number of minimum subsets, say polynomial.

*(please read on if you need motivations to the problem! The part below contains some technical details to the usage of the lemma, and some applications to log-space computations.)*

---

## Motivation

I am working on the problems in log-space computations, precisely the relation between classes $\mathsf{NL}$, $\mathsf{UL}$, and many other classes below and in between.
Consider the above lemma, which requires $O(n \log n)$ random bits if we assign weights to $U$ accordingly. A random-bit-saving version of the lemma is presented in [this paper](http://portal.acm.org/citation.cfm?id=167213) by Chari et al., which states:

> **Lemma.** Let $U$ be a set of size $n$, and $\mathcal{F}$ be a non-empty family containing elements which are the subsets of $U$. There is a way of assigning weights in $[n^7]$ on $U$ with $O(\log|F|+\log n)$ random bits, such that there exist a unique minimum weighted subset in $\mathcal{F}$ with probability at least $1/4$.

That gives us an $\mathsf{USPACE}[O(\log|F|+\log n)]$ algorithm for reachability. Of course this is a pity bound, since by [Savitch's theorem](http://en.wikipedia.org/wiki/Savitch%27s_theorem) we have $\mathsf{NL} \subseteq \mathsf{L}^2 \subseteq \mathsf{UL}^2$.

But what if we consider the reachability problem with a restriction that there are at most $f(n)$ paths from the source to any node in the graph? This defines the problem $\mathtt{Reach}[f(n)]$, and we have $\mathtt{Reach}[2^n]$ to be the normal reachability problem. By setting $f(n)$ a polynomial, applying the above lemma together with an $\mathsf{UL}$-algorithm for reachability in graphs with a minimum unique path (see [the paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.2546&rep=rep1&type=pdf) for more details), we can solve $\mathtt{Reach}[n^{O(1)}]$ in $\mathsf{UL}$. (The result occurs in [this recent paper](http://cse.unl.edu/~rtewari/unamb.pdf). In fact they use a stronger version of the lemma, which isolates every paths in the graph by a constructive way.)

If a weaker isolation lemma is known to have less restrictions on either the size of $\mathcal{F}$, or the number of random bits being used, we can provide better bounds on the problem $\mathtt{Reach}[f(n)]$, with the help of some modifications to solve reachability in graphs with few minimum paths. Hopefully if the lemma is *weak* enough to set $f(n) = 2^n$, and we can obtain some better bounds about the important class $\mathsf{NL}$.

Any comments on the proof techniques or obstacles will give insight to the question, and I would like to know that whether this idea has a tiny little chance of success, or it is just a completely impossible concept.

**Tags:** cc.complexity-theory, randomness

> **Comments:**
> **username_1**: This is an interesting variant.  If you limit the number to $\operatorname{poly}(n)$, then you would likely be placing NL in FewL (non-deterministic log-space with at most a polynomial number of accepting paths).  
> **username_0**: @Derrick: That is pretty much the motivation of this question. :) But that will need some additional criteria, say the number of random bits being used should be $O(\log n)$, and we can not pose any constrain on the size of *F*. Still some weaker results may be obtained if we have further insights to this variant. Any idea?  
> **username_1**: I am unsure that even with $O(\log n)$ random bits that the isolation can be derandomized, since the resulting weight function would need to be deterministically verified to be min-unique, which is hard.  
> **username_0**: Maybe verify the min-uniqueness (min-fewness?) deterministically is too strict, some variant of inductive counting technique which runs in FewL may do the job, just like the one in the result NL/poly = UL/poly.  
> **username_2**: Would you please explain why this "weak isolation lemma" is useful?  
> **username_0**: @username_2: Sure, since there are some direct applications to the weak lemma, and maybe the current version of the article is not well-written, I'll revise the entire question to make it both more attractive and self-contained.  
> **username_2**: That would be great!  

---

## 0 answers

