The isolation lemma of Mulmuley et al cite{MVV87} is an important
tool in the design of randomized algorithms and has played an
important role in several nontrivial complexity upper bounds. On
the other hand, polynomial identity testing is a well-studied
algorithmic problem with efficient randomized algorithms and the
problem of obtaining efficient emph{deterministic} identity tests
has received a lot of attention recently. The goal of this note is
to compare the isolation lemma with polynomial identity testing:
begin{enumerate}
item We show that derandomizing reasonably restricted versions of the
isolation lemma implies circuit size lower bounds. We derive the
circuit lower bounds by examining the connection between the
isolation lemma and polynomial identity testing. We give a
randomized polynomial-time identity test for noncommutative circuits
of polynomial degree based on the isolation lemma. Using this
result, we show that derandomizing the isolation lemma implies
noncommutative circuit size lower bounds. For the commutative case,
a stronger derandomization hypothesis allows us to construct an
explicit multilinear polynomial that does not have subexponential
size commutative circuits. The restricted versions of the isolation
lemma we consider are natural and would suffice for the standard
applications of the isolation lemma.

item From the result of Klivans-Spielman cite{KS01} we observe that
there is a randomized polynomial-time identity test for commutative
circuits of polynomial degree, also based on a more general
isolation lemma for linear forms. Consequently, derandomization of
(a suitable version of) this isolation lemma implies that either
$NEXPnotsubset P/poly$ or the Permanent over $Z$ does not have
polynomial-size arithmetic circuits.
end{enumerate}

The isolation lemma of Mulmuley et al \cite{MVV87} is an important
tool in the design of randomized algorithms and has played an
important role in several nontrivial complexity upper bounds. On
the other hand, polynomial identity testing is a well-studied
algorithmic problem with efficient randomized algorithms and the
problem of obtaining efficient \emph{deterministic} identity tests
has received a lot of attention recently. The goal of this note is
to compare the isolation lemma with polynomial identity testing:
\begin{enumerate}
\item We show that derandomizing reasonably restricted versions of the
isolation lemma implies circuit size lower bounds. We derive the
circuit lower bounds by examining the connection between the
isolation lemma and polynomial identity testing. We give a
randomized polynomial-time identity test for noncommutative circuits
of polynomial degree based on the isolation lemma. Using this
result, we show that derandomizing the isolation lemma implies
noncommutative circuit size lower bounds. For the commutative case,
a stronger derandomization hypothesis allows us to construct an
explicit multilinear polynomial that does not have subexponential
size commutative circuits. The restricted versions of the isolation
lemma we consider are natural and would suffice for the standard
applications of the isolation lemma.

\item From the result of Klivans-Spielman \cite{KS01} we observe that
there is a randomized polynomial-time identity test for commutative
circuits of polynomial degree, also based on a more general
isolation lemma for linear forms. Consequently, derandomization of
(a suitable version of) this isolation lemma implies that either
$\NEXP\not\subset \P/\poly$ or the Permanent over $\Z$ does not have
polynomial-size arithmetic circuits.
\end{enumerate}

The isolation lemma of Mulmuley et al \cite{MVV87} is an
important tool in the design of randomized algorithms and has played an
important role in several nontrivial complexity upper bounds. On
the other hand, polynomial identity testing is a well-studied
algorithmic problem with efficient randomized algorithms and the
problem of obtaining efficient \emph{deterministic} identity tests
has received a lot of attention recently. The goal of this note is
to compare the isolation lemma with polynomial identity testing:

1. We show that derandomizing reasonably restricted versions of the
isolation lemma implies circuit size lower bounds. We derive the
circuit lower bounds by examining the connection between the
isolation lemma and polynomial identity testing. We give a
randomized polynomial-time identity test for noncommutative circuits
of polynomial degree based on the isolation lemma. Using this
result, we show that derandomizing the isolation lemma implies
noncommutative circuit size lower bounds. The restricted versions of
the isolation lemma we consider are natural and would suffice for
the standard applications of the isolation lemma.

2. From the result of Klivans-Spielman \cite{KS01} we observe that
there is a randomized polynomial-time identity test for commutative
circuits of polynomial degree, also based on a more general
isolation lemma for linear forms. Consequently, derandomization of
(a suitable version of) this isolation lemma implies that either
$\NEXP\not\subset \P/\poly$ or the Permanent over $\Z$ does not have
polynomial-size arithmetic circuits.

We give a randomized polynomial-time identity test for
noncommutative circuits of polynomial degree based on the isolation
lemma. Using this result, we show that derandomizing the isolation
lemma implies noncommutative circuit size lower bounds. More
precisely, we consider two restricted versions of the isolation
lemma and show that derandomizing each of them implies nontrivial
circuit size lower bounds for noncommutative circuits. These
restricted versions of the isolation lemma are natural and would
suffice for the standard applications of the isolation lemma.