Skip to content

The Isolation Lemma and Beyond

July 1, 2009
tags: , , , , , , ,


The isolation lemma and recent applications

Picture 3

Ketan Mulmuley, Umesh Vazirani, and Vijay Vazirani are three great theorists: Ketan is most famous these days for his attempts to use algebraic geometry to prove lower bounds, Umesh for his seminal work on quantum computing, and Vijay for his many contributions to the theory of approximation algorithms–his book on this is already a classic.

Today I would like to talk about an old result of theirs: the famous Isolation Lemma. This beautiful result has had a huge impact on many parts of complexity theory. The reason for this post is that there have been recent results either using the lemma or using related lemmas. Also their famous result is just another example of great results that have not been awarded the accolades they deserve. Oh well.

Umesh and Vijay were one of the early pairs of brothers in the theory of computing. I think the first pair was probably the Fischer brothers, Michael Fischer and Patrick Fischer. Now we have many more pairs of siblings, who both work in the theory of computing. I am currently working with one half of a pair of identical twins. Is that right?

The Isolation Lemma

The Isolation Lemma (IL) is, in my opinion, one of those results that seems magical. There are countless examples of the power of randomization, but there is something very surprising about this result.

Let {X} be a set of {n} points, and let {\cal F} be a family of subsets of {X}. Assign a weight {w(x)} to each point, and define the weight of a set {E} as

\displaystyle w(E) = \sum_{x \in E} w(x).

If the set with the minimum weight is unique, then call the weight function {w} isolating.

Lemma: Let {\cal F} be a family of {n} element subsets of the set {X}. Then,

\displaystyle \text{Prob}_{w}[ w \text{ is isolating for } {\cal F}] \ge 1-\frac{n}{N}.

Here {w} the random function from {X} to {1,\dots,N}.

That there is no dependence on the structure or lack of structure of the family {\cal F} is surprising. There are many nice proofs of IL–see this for one.

Applications

There are many classic applications of the IL. Of course before the IL there was the beautiful paper of Leslie Valiant and Vijay on unique SAT, which was used in Seinosuke Toda’s famous theorem reducing the polynomial hierarchy to {\mathsf{PP}}.

In the last few years there have been a number of quite different applications. I would like to highlight a few of these.

{\bullet} One interesting application of the IL technology is to Watermarking. This is the problem of hiding information into either hardware or software, so that intellectual property is protected. Rupak Majumdar and Jennifer Wong use the unique SAT result in particular to help create a “watermark.” I like this paper, since it shows the wide range and power of the IL.

{\bullet} Another direction is to use the IL to get identity testing results, which is what Vikraman Arvind, Partha Mukhopadhyay, and Srikanth Srinivasan do in their wonderful paper. They give a new identity test based on IL for non-commutative polynomials:

Theorem: Let {f} be a polynomial over {n} non-commuting variables given by an arithmetic circuit of size {m}. Let {d} be the upper bound on the degree of {f}. Then there is a randomized algorithm which runs in time {\text{poly}(n,m,d)} and can test whether {f \equiv 0}.

{\bullet} Last, I would like to mention the work of Ryan Williams that does not use the IL directly. However, his work uses a lemma that is similar in spirit to the IL. His main result is:

Theorem: There is a randomized algorithm that determines if a given graph has a simple path of length at least {k} in

\displaystyle O(2^{k}\cdot \text{poly}(n,k))

time.

See his pretty paper for the details. The main lemma–actually in the paper it’s Theorem 3.1–is an kind of isolation result. He encodes the graph problem as the problem of determining whether or not a polynomial {P(x_{1},\dots,x_{k})} has a multilinear term. That is a term of the form {xyz} and not {xy^{6}wt}. Since the polynomial is defined by an arithmetic circuit, it is impossible to determine this by brute force–there will be an exponential number of terms in general.

What Ryan shows is this: evaluate the polynomial at a random element from a certain group algebra. Then, all non-multilinear terms evaluate to zero, and some multilinear terms survive. Finally, he makes use of randomness again to detect this. I think that this is in the spirit of the IL, randomness is used to isolate the multilinear terms from the non-multilinear terms. Take a look at the paper and see if you agree.

Open Problems

One of the on-going questions is de-randomizing the Isolation Lemma in specific cases. Since there are {2^{2^{n}}} set systems {{\cal F}} general de-randomization appears to be impossible.

Another obvious related question is: what structure on the family {{\cal F}} would imply a sharper bound, or allow de-randomization?

from → History, P=NP, People, Proofs
14 Comments leave one →
  1. jonkatz permalink
    July 1, 2009 8:58 am

    A small typo in the lemma: the sets in F need not be n-element sets, they can have arbitrary size. (n denotes the size of the ground set X.)

    Reply
  2. aravind permalink
    July 1, 2009 9:16 am

    Hi Dick,

    We have a paper (STOC ’93, SICOMP ’95) which shows that one gets a better randomness complexity if an upper-bound Z on the size of the family F is known: we need O(log n + log Z) random bits. (In the context of general set-systems, we also show this bound to be tight for the IL.) We spent much time to improve this for the specific context of matching, to no avail.

    Reply
    • rjlipton permalink*
      July 1, 2009 3:13 pm

      Wonderful. I am sorry I missed referencing this.

      Reply
  3. Srikanth Srinivasan permalink
    July 1, 2009 11:36 am

    Hi

    A caveat about the result of Arvind, Mukhopadhyay, and Srinivasan that you mention: their algorithm runs in time polynomial in n,m,d AND the number of monomials appearing in the polynomial. In other words, the algorithm is polynomial time only when the non-commutative polynomial computed by the input circuit is sparse. The existence of deterministic identity testing algorithms for the general case remains open, as far as I know.

    Reply
    • rjlipton permalink*
      July 1, 2009 3:15 pm

      Yes, I should have stated the theorem more clearly. Still a very cool result. Does the general case imply anything that you know about?

      Reply
      • anon permalink
        July 1, 2009 4:47 pm

        Yes that is right.
        And I guess the recent famous twins in TCS are the Makarychevs (Charikar’s students)? Are there more?

      • tcsamateur permalink
        July 2, 2009 1:58 am

        A deterministic algorithm for the general case would imply some sort of circuit lower bounds in the Kabanets-Impagliazzo sense. Pretty much the same proof (as that of Kabanets-Impagliazzo) shows that if there is an efficient deterministic identity testing algorithm for the Polynomial Identity testing problem for non-commutative circuits, then either \mathrm{NEXP} \subsetneq \mathrm{P}/\mathrm{poly} or the non-commutative Permanent does not have polynomial sized arithmetic circuits. Since we don’t yet have explicit lower bounds for general non-commutative circuits, that is something.

      • Partha Mukhopadhyay permalink
        July 2, 2009 7:47 am

        Hi,

        A deterministic polynomial-time algorithm for identity testing of non-commutative circuits will imply strong lower bound result for non-commutative circuits (analogous to Impagliazzo-Kabanets result appeared in STOC 2001 and originally stated for commutative circuits).
        In the non-commutative model, the strong lower bound is only known for non-commutative formulas (Nisan 91). AMS’08 paper gives a deterministic polynomial-time algorithm for non-commutative sparse polynomials only, as Srikanth mentioned. In another paper with Arvind (in RANDOM 2008), we show a new randomized polynomial-time identity testing algorithm for non-commutative circuits using isolation lemma.

        Thanks,
        Partha

      • rjlipton permalink*
        July 2, 2009 8:08 am

        I have an old, many author, paper that shows that the random self-reduction ideas also apply to non-commutative polynomials. I wonder if there are any connections. I have not thought about this for a long time.

        Anyway thanks for your comment. Very pretty work.

  4. rjlipton permalink*
    July 1, 2009 6:18 pm

    No. There are more. My half is Atish Das Sarma, his other is at Stanford.

    Reply
  5. none permalink
    July 2, 2009 1:49 am

    http://blog.computationalcomplexity.org/2009/02/baseball-families-and-math-families.html mentions some other pairs of brothers in CS theory.

    Reply
  6. KWRegan permalink
    May 29, 2012 9:51 pm

    Umesh and Vijay each visited me in Oxford on their way to/from India when we were all students, Vijay twice.

    Reply

Trackbacks

  1. Twitted by ashalynd
  2. Is there any research on the notion of weak isolation? | Q&A System

Leave a Reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading