3
$\begingroup$

(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, 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", have been used to prove many amazing results like an RNC-algorithm for matching in the above paper; Valiant–Vazirani theorem which is a randomized reduction from NP problems to USAT; NL/poly=UL/poly; and many others. Surveys and introduction in blogs 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. 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 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 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 for more details), we can solve $\mathtt{Reach}[n^{O(1)}]$ in $\mathsf{UL}$. (The result occurs in this recent paper. 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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Derrick Stolee Dec 10 '10 at 18:58
  • $\begingroup$ @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? $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 10 '10 at 19:13
  • 1
    $\begingroup$ Would you please explain why this "weak isolation lemma" is useful? $\endgroup$ – Dai Le Dec 11 '10 at 6:08
  • 1
    $\begingroup$ @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. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 11 '10 at 6:20
  • 1
    $\begingroup$ That would be great! $\endgroup$ – Dai Le Dec 11 '10 at 6:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.