Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size

Introduction

[MVV87] Let $U$ be an universe of size $n$ and $\mathcal{F}$ be any family of subsets of $U$. Let $w:U\rightarrow[2n]$ denote a weight assignment function to elements of $U$. Then,

where the weight function $w$ is picked uniformly at random.

In the seminal paper [MVV87] Mulmuley et al apply the isolation lemma to give a randomized NC algorithm for computing maximum cardinality matchings for general graphs (also see [ARZ99]). Since then the isolation lemma has found several other applications. For example, it is crucially used in the proof of the result that $\mbox{\rm NL}\subset\mbox{\rm UL}/\mbox{\rm poly}$ [AR00] and in designing randomized NC algorithms for linear representable matroid problems [NSV94]. It is also known that the isolation lemma can be used to prove the Valiant-Vazirani lemma that SAT is many-one reducible via randomized reductions to USAT.

Whether the matching problem is in deterministic NC, and whether $\mbox{\rm NL}\subseteq\mbox{\rm UL}$ are outstanding open problems. Thus, the question whether the isolation lemma can be derandomized is clearly important.

As noted in [Agr07], it is easy to see by a counting argument that the isolation lemma can not be derandomized, in general, because there are $2^{2^{n}}$ set systems $\mathcal{F}$. More formally, the following is observed in [Agr07].

[Agr07] The Isolation Lemma can not be fully derandomized if we allow weight functions $w:U\rightarrow[n^{c}]$ for a constant $c$ (i.e. weight functions with a polynomial range). More precisely, for any polynomially bounded collection of weight assignments $\{w_{i}\}_{i\in[n^{c_{1}}]}$ with weight range $[n^{c}]$, there exists a family $\mathcal{F}$ of $[n]$ such that for all $j\in[n^{c_{1}}]$, there exists two minimal weight subsets with respect to $w_{j}$.

However that does not rule out the derandomization of any special usage of the isolation lemma. Indeed, for all applications of the isolation lemma (mentioned above, for instance) we are interested only in exponentially many set systems $\mathcal{F}\subseteq 2^{U}$.

We make the setting more precise by giving a general framework. Fix the universe $U=[n]$ and consider an $n$-input boolean circuit $C$ where $\it size(C)=m$. The set $2^{U}$ of all subsets of $U$ is in a natural $1$-$1$ correspondence with the length $n$-binary strings $\{0,1\}^{n}$: each subset $S\subseteq U$ corresponds to its characteristic binary string $\chi_{S}\in\{0,1\}^{n}$ whose $i^{th}$ bit is $1$ iff $i\in S$. Thus the $n$-input boolean circuit $C$ implicitly defines the set system

As an easy consequence of Lemma 1.1 we have the following.

Let $U$ be an universe of size $n$ and $C$ be an $n$-input boolean circuit of size $m$. Let $\mathcal{F}_{C}\subseteq 2^{U}$ be the family of subsets of $U$ defined by circuit $C$. Let $w:U\rightarrow[2n]$ denote a weight assignment function to elements of $U$. Then,

where the weight function $w$ is picked uniformly at random. Furthermore, there is a collection of weight functions $\{w_{i}\}_{1\leq i\leq p(m,n)}$, where $p(m,n)$ is a fixed polynomial, such that for each $\mathcal{F}_{C}$ there is a weight function $w_{i}$ w.r.t. which there is a unique minimum weight set in $\mathcal{F}_{C}$.

Lemma 1.3 allows us to formulate two natural and reasonable derandomization hypotheses for the isolation lemma.

Hypothesis 1. There is a deterministic algorithm $\mathcal{A}_{1}$ that takes as input $(C,n)$, where $C$ is an $n$-input boolean circuit, and outputs a collection of weight functions $w_{1},w_{2},\cdots,w_{t}$ such that $w_{i}:[n]\rightarrow[2n]$, with the property that for some $w_{i}$ there is a unique minimum weight set in the set system $\mathcal{F}_{C}$. Furthermore, $\mathcal{A}_{1}$ runs in time subexponential in $\it size(C)$.

Hypothesis 2. There is a deterministic algorithm $\mathcal{A}_{2}$ that takes as input $(m,n)$ in unary and outputs a collection of weight functions $w_{1},w_{2},\cdots,w_{t}$ such that $w_{i}:[n]\rightarrow[2n]$, with the property that for each size $m$ boolean circuit $C$ with $n$ inputs there is some weight function $w_{i}$ w.r.t. which $\mathcal{F}_{C}$ has a unique minimum weight set. Furthermore, $\mathcal{A}_{2}$ runs in time polynomial in $m$.

Clearly, Hypothesis 2 is stronger than Hypothesis 1. It demands a “black-box” derandomization in the sense that $\mathcal{A}_{2}$ efficiently computes a collection of weight functions that will work for any set system in $2^{U}$ specified by a boolean circuit of size $m$.

Notice that a random collection $w_{1},\cdots,w_{t}$ of weight functions will fulfil the required property of either hypotheses with high probability. Thus, the derandomization hypotheses are plausible. Indeed, it is not hard to see that suitable standard hardness assumptions that yield pseudorandom generators for derandomizing BPP would imply these hypotheses. We do not elaborate on this here. In this paper we show the following consequences of Hypotheses 1 and 2.

Hypothesis 1 implies that either $\mbox{\small\rm NEXP}\not\subset\mbox{\rm P}/\mbox{\rm poly}$ or the Permanent does not have polynomial size noncommutative arithmetic circuits.

These two results are a consequence of an identity testing algorithm for noncommutative circuits that is based on the isolation lemma. This algorithm is based on ideas from [AMS08] where we used automata theory to pick matrices from a suitable matrix ring and evaluate the given arithmetic circuit on these matrices. In the next section, we describe the background and then give the identity test in the following section.

Notice that derandomizing the isolation lemma in specific applications like the $\rm RNC$ algorithm for matchings [MVV87] and the containment $\mbox{\rm NL}\subseteq\mbox{\rm UL}/\mbox{\rm poly}$ [AR00] might still be possible without implying such circuit size lower bounds.

Our result in this paper is similar in flavor to the Impagliazzo-Kabanets result [KI03], where for commutative polynomial identity testing they show that derandomizing polynomial identity testing implies circuit lower bounds. Specifically, it implies that either $\mbox{\small\rm NEXP}\not\subset\mbox{\rm P/poly}$ or the integer Permanent does not have polynomial-size arithmetic circuits.

In [AMS08] we have observed that an analogous result also holds in the noncommutative setting. I.e., if noncommutative PIT has a deterministic polynomial-time algorithm then either $\mbox{\small\rm NEXP}\not\subset\mbox{\rm P/poly}$ or the noncommutative Permanent function does not have polynomial-size noncommutative circuits.

The connection that we show here between derandomizing the isolation lemma and noncommutative circuit size lower bounds is based on the above observation and our noncommutative polynomial identity test based on the isolation lemma.

Klivans and Spielman [KS01] apply a more general form of the isolation lemma to obtain a polynomial identity test (in the commutative) case. This lemma is stated below.

[KS01, Lemma 4] Let $L$ be any collection of linear forms over variables $z_{1},z_{2},\cdots,z_{n}$ with integer coefficients in the range $\{0,1,\cdots,K\}$. If each $z_{i}$ is picked independently and uniformly at random from $\{0,1,\cdots,2Kn\}$ then with probability at least $1/2$ there is a unique linear form from $C$ that attains minimum value at $(z_{1},\cdots,z_{n})$.

We can formulate a restricted version of this lemma similar to Lemma 1.3 that will apply only to sets of linear forms $L$ accepted by a boolean circuit $C$. More precisely, an integer vector $(\alpha_{1},\cdots,\alpha_{n})$ such that $\alpha_{i}\in\{0,\cdots,K\}$ is in $L$ if and only if $(\alpha_{1},\cdots,\alpha_{n})$ is accepted by the boolean circuit $C$.

Thus, for this form of the isolation lemma we can formulate another derandomization hypothesis analogous to Hypothesis 1 as follows.

Hypothesis 3. There is a deterministic algorithm $\mathcal{A}_{3}$ that takes as input $(C,n,K)$, where $C$ is a boolean circuit that takes as input $(\alpha_{1},\cdots,\alpha_{n})$ such that $\alpha_{i}\in\{0,\cdots,K\}$, and outputs a collection of weight functions $w_{1},w_{2},\cdots,w_{t}$ such that $w_{i}:[n]\rightarrow[2Kn]$, with the property that for some weight vector $w_{i}$ there is a unique linear form $(\alpha_{1},\cdots,\alpha_{n})$ accepted by $C$ which attains the minimum value $\sum_{j=1}^{n}w_{i}(j)\alpha_{j}$. Furthermore, $\mathcal{A}_{3}$ runs in time subexponential in $\it size(C)$.

Automata Theory background

For a string $w=w_{1}w_{2}\cdots w_{k}\in\{0,1\}^{*}$ we define $M_{w}$ to be the matrix product $M_{w_{1}}M_{w_{2}}\cdots M_{w_{k}}$. If $w$ is the empty string, define $M_{w}$ to be the identity matrix of dimension $|Q|\times|Q|$. Let $\delta_{w}$ denote the natural extension of the transition function to $w$; if $w$ is the empty string, $\delta_{w}$ is simply the identity function. We have

Thus, $M_{w}$ is also a matrix of zeros and ones for any string $w$. Also, $M_{w}(q_{0},q_{f})=1$ if and only if $w$ is accepted by the automaton $A$.

This subsection is reproduced from [AMS08] to make this paper self-contained.

We observe the following property: the matrix output $M_{out}$ of $C$ on $A$ is determined completely by the polynomial $f$ computed by $C$; the structure of the circuit $C$ is otherwise irrelevant. This is important for us, since we are only interested in $f$. In particular, the output is always when $f\equiv 0$.

Proof. The proof is an easy consequence of the definitions and the properties of the matrices $M_{w}$ stated in Section 2. Note that $M_{out}=f(M_{v_{1}},\cdots,M_{v_{n}})$. But $f(M_{v_{1}},\cdots,M_{v_{n}})=\sum_{i=1}^{s}c_{i}M_{w_{i}}$, where $w_{i}=v_{i_{1}}\cdots v_{i_{d_{i}}}$ is the binary string representing monomial $m_{i}$. By Equation 1, we know that $M_{w_{i}}(q_{0},q_{f})$ is $1$ if $w_{i}$ is accepted by $A$, and otherwise. Adding up, we obtain the result.

We now explain the role of the automaton $A$ in testing if the polynomial $f$ computed by $C$ is identically zero. Our basic idea is to design an automaton $A$ that accepts exactly one word from among all the words that correspond to the nonzero terms in $f$. This would ensure that $M_{out}(q_{0},q_{f})$ is the nonzero coefficient of the monomial filtered out. More precisely, we will use the above theorem primarily in the following form, which we state as a corollary.

If $A$ rejects every string corresponding to a monomial in $f$, then $M_{out}(q_{0},q_{f})=0$.

If $A$ accepts exactly one string corresponding to a monomial in $f$, then $M_{out}(q_{0},q_{f})$ is the nonzero coefficient of that monomial in $f$.

Moreover, $M_{out}$ can be computed in time $\mbox{\rm poly}(|C|,|A|,n)$.

Proof. Both points ($1$) and ($2$) are immediate consequences of the above theorem. The complexity of computing $M_{out}$ easily follows from its definition.

Another interesting corollary to the above theorem is the following.

Proof. Apply Corollary 2.2 with $A$ being any standard automaton that accepts the string corresponding to monomial $m$ and rejects every other string. Clearly, $A$ can be chosen so that $A$ has a unique accepting state and $|A|=O(nd_{m})$.

Noncommutative identity test based on isolation lemma

We now describe a new identity test for noncommutative circuits based on the isolation lemma. It is directly based on the results from [AMS08]. This is conceptually quite different from the randomized identity test of Bogdanov and Wee [BW05].

Proof. Let $[d]=\{1,2,\cdots,d\}$ and $[n]=\{1,2,\cdots,n\}$. Consider the set of tuples $U=[d]\times[n]$. Let $v=x_{i_{1}}x_{i_{2}}\cdots x_{i_{t}}$ be a nonzero monomial of $f$. Then the monomial can be identified with the following subset $S_{v}$ of $U$ :

Let $\mathcal{F}$ denotes the family of subsets of $U$ corresponding to the nonzero monomials of $f$ i.e,

By the Isolation Lemma we know that if we assign random weights from $[2dn]$ to the elements of $U$, with probability at least $1/2$, there is a unique minimum weight set in $\mathcal{F}$. Our aim will be to construct a family of small size automatons which are indexed by weights $w\in[2nd^{2}]$ and $t\in[d]$, such that the automata $A_{w,t}$ will precisely accept all the strings (corresponding to the monomials) $v$ of length $t$, such that the weight of $S_{v}$ is $w$. Then from the isolation lemma we will argue that the automata corresponding to the minimum weight will precisely accept only one string (monomial). Now for $w\in[2nd^{2}]$, and $t\in[d]$, we describe the construction of the automaton $A_{w,t}=(Q,\Sigma,\delta,q_{0},F)$ as follows: $Q=[d]\times[2nd^{2}]\cup\{(0,0)\}$, $\Sigma=\{x_{1},x_{2},\cdots,x_{n}\}$, $q_{0}=\{(0,0)\}$ and $F=\{(t,w)\}$. We define the transition function $\delta:Q\times\Sigma\rightarrow Q$,

where $W$ is the random weight assign to $(i+1,j)$. Our automata family $\mathcal{A}$ is simply,

Now for each of the automaton $A_{w,t}\in\mathcal{A}$, we mimic the run of the automaton $A_{w,t}$ on the circuit $C$ as described in Section 2. If the output matrix corresponding to any of the automaton is nonzero, our algorithm declares $f\neq 0$, otherwise declares $f\equiv 0$.

Noncommutative identity testing and circuit lower bounds

For commutative circuits, Impagliazzo and Kabanets [KI03] have shown that derandomizing PIT implies circuit lower bounds. It implies that either $\mbox{\small\rm NEXP}\not\subset\mbox{\rm P/poly}$ or the integer Permanent does not have polynomial-size arithmetic circuits.

In [AMS08] we have observed that this also holds in the noncommutative setting. I.e., if noncommutative PIT has a deterministic polynomial-time algorithm then either $\mbox{\small\rm NEXP}\not\subset\mbox{\rm P/poly}$ or the noncommutative Permanent function does not have polynomial-size noncommutative circuits. We note here that noncommutative circuit lower bounds are sometimes easier to prove than for commutative circuits. E.g. Nisan [N91] has shown exponential-size lower bounds for noncommutative formula size and further results are known for pure noncommutative circuits [N91, RS05]. However, proving superpolynomial size lower bounds for general noncommutative circuits computing the Permanent has remained an open problem.

To keep this paper self contained, we briefly recall the discussion from [AMS08].

The noncommutative Permanent function $Perm(x_{1},\cdots,x_{n})\in R\{x_{1},\cdots,x_{n}\}$ is defined as

Let SUBEXP denote $\cap_{\epsilon>0}\rm DTIME(2^{n^{\epsilon}})$ and NSUBEXP denote $\cap_{\epsilon>0}\rm NTIME(2^{n^{\epsilon}})$.

The Results

We are now ready to prove our first result. Suppose the derandomization Hypothesis 1 holds (as stated in the introduction): i.e. suppose there is a deterministic algorithm $\mathcal{A}_{1}$ that takes as input $(C,n)$ where $C$ is an $n$-input boolean circuit and in subexponential time computes a set of weight functions $w_{1},w_{2},\cdots,w_{t}$, $w_{i}:[n]\rightarrow[2n]$ such that the set system $\mathcal{F}_{C}$ defined by the circuit $C$ has a unique minimum weight set w.r.t. at least one of the weight functions $w_{i}$.

Let $C^{\prime}(x_{1},x_{2},\cdots,x_{n})$ be a noncommutative arithmetic circuit of degree $d$ bounded by a polynomial in $\it size(C^{\prime})$. By Corollary 2.3, there is a deterministic polynomial-time algorithm that takes as input $C^{\prime}$ and a monomial $m$ of degree at most $d$ and accepts if and only if the monomial $m$ has nonzero coefficient in the polynomial computed by $C^{\prime}$. Thus, we have a boolean circuit $C$ of size polynomial in $\it size(C^{\prime})$ that accepts only the (binary encodings of) monomials $x_{i_{1}}x_{i_{2}}\cdots x_{i_{k}}$, $k\leq d$ that have nonzero coefficients in the polynomial computed by $C^{\prime}$. Now, as a consequence of Theorem 3.1 and its proof we have a deterministic subexponential algorithm for checking if $C^{\prime}\equiv 0$, assuming algorithm $\mathcal{A}_{1}$ exists. Namely, we compute the boolean circuit $C$ from $C^{\prime}$ in polynomial time. Then, invoking algorithm $\mathcal{A}_{1}$ with $C$ as input we compute at most subexponentially many weight functions $w_{1},\cdots,w_{t}$. Then, following the proof of Theorem 3.1 we construct the automata corresponding to these weight functions and evaluate $C^{\prime}$ on the matrices that each of these automata define in the prescribed manner. By assumption about algorithm $\mathcal{A}_{1}$, if $C^{\prime}\not\equiv 0$ then one of these $w_{i}$ will give matrix inputs for the variables $x_{j},1\leq j\leq n$ on which $C^{\prime}$ evaluates to a nonzero matrix. We can now show the following theorem.

If the subexponential time algorithm $\mathcal{A}_{1}$ satisfying Hypothesis 1 exists then noncommutative identity testing is in SUBEXP which implies that either $\mbox{\small\rm NEXP}\not\subset\mbox{\rm P}/\mbox{\rm poly}$ or the Permanent does not have polynomial size noncommutative circuits.

Proof. The result is a direct consequence of the discussion preceding the theorem statement and Theorem 4.1.

We now turn to the result under the stronger derandomization Hypothesis 2 (stated in the introduction). More precisely, suppose there is a deterministic algorithm $\mathcal{A}_{2}$ that takes as input $(m,n)$ and in time polynomial in $m$ computes a set of weight functions $w_{1},w_{2},\cdots,w_{t}$, $w_{i}:[n]\rightarrow[2n]$ such that for each $n$-input boolean circuit $C$ of size $m$, the set system $\mathcal{F}_{C}$ defined by the circuit $C$ has a unique minimum weight set w.r.t. at least one of the weight functions $w_{i}$. We show that there is an explicit polynomialBy explicit we mean that the coefficients of $f$ are computable in time exponential in $n$. $f(x_{1},\cdots,x_{n})$ in noncommuting variables $x_{i}$ that does not have subexponential size noncommutative circuits.

Proof. Let $T_{n}$ denote the set of all sequences $(i_{1},i_{2},\cdots,i_{n})$, for $i_{j}\in[n]$, $1\leq j\leq n$. For each such sequence $\alpha=(i_{1},i_{2},\cdots,i_{n})\in T_{n}$ let $m_{\alpha}$ denote the monomial $x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}$. Now, we write

where we will pick the scalars $c_{\alpha}$ appropriately so that the polynomial $f$ has the claimed property. Suppose $\mathcal{A}_{2}$ runs in time $m^{c}$ for constant $c>0$, where $m$ denotes the size bound of the boolean circuit $C$ defining set system $\mathcal{F}_{C}$. Notice that the number $t$ of weight functions is bounded by $m^{c}$. As explained in Theorem 3.1, each weight function will give rise to a collection of $2n^{4}$ automata $\mathcal{A}_{k}$, each of which will prescribe matrices of dimension at most $r=\mbox{\rm poly}(n)$ to be assigned for the input variables $x_{j},1\leq j\leq n$. Call these matrices $M^{(k)}_{i,j}$. For each weight function $w_{i}$ write down linear equations for each $k\in[2n^{4}]$.

This will actually give us a system of at most $2n^{4}r^{2}$ linear equations in the unknown scalars $c_{\alpha}$. Since there are $t\leq m^{c}$ weight functions in all, all the linear constraints put together give us a system of at most $2n^{4}r^{2}m^{c}$ linear equations. Now, the number of distinct (noncommuting) monomials $m_{\alpha}$ is $n^{n}=2^{n\lg n}$ which asymptotically exceeds $2n^{4}r^{2}m^{c}$ for $m=2^{o(n\lg n)}$, since $r$ is polynomially bounded. Thus, the system of linear equations has a nontrivial solution in the $c_{\alpha}$’s that can be computed using Gaussian elimination in time exponential in $n$.

Notice that the polynomial $f(x_{1},\cdots,x_{n})$, defined by the solution to the $c_{\alpha}$’s, is a nonzero polynomial. We claim that $f$ cannot have a noncommutative circuit of size $2^{o(n\lg n)}$. Assume to the contrary that $C^{\prime}(x_{1},\cdots,x_{n})$ is a noncommutative circuit of size $s=2^{o(n\lg n)}$ for $f$. Then, by Corollary 2.3 there is an $n^{\prime}$-input boolean circuit $C$ of size $m=s^{O(1)}=2^{o(n\lg n)}$ that accepts precisely the (binary encodings) of those monomials that are nonzero in $C^{\prime}$. Let $w_{1},\cdots,w_{t}$ be the weight functions output by $\mathcal{A}_{2}$ for input $(m,n^{\prime})$. By Hypothesis 2, for some weight function $w_{i}$ and some $k\in[2n^{4}]$ the circuit $C^{\prime}$ must be nonzero on matrices $M^{(k)}_{i,j}$. However, $f$ evaluates to zero, by construction, on the matrix inputs prescribed by all the weight functions $w_{1},\cdots,w_{t}$. This is a contradiction to the assumption and it completes the proof.

We can formulate both Hypothesis 1 and Hypothesis 2 more generally by letting the running time of algorithms $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ be a function $t(m,n)$. We will then obtain suitably quantified circuit lower bound results as consequence.

We now show that under the derandomization Hypothesis 3 (stated in the introduction) we can obtain a stronger consequence than Theorem 5.1.

Coming to the proof of this theorem, if $\mbox{\small\rm NEXP}\not\subset\mbox{\rm P}/\mbox{\rm poly}$ then we are done. So, suppose $\mbox{\small\rm NEXP}\subset\mbox{\rm P}/\mbox{\rm poly}$. Notice that given any monomial $x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}$ of total degree bounded by $d$ we can test if it is a nonzero monomial of $\hat{C}$ in exponential time ( explicitly listing down the monomials of the polynomial computed by $\hat{C}$). Therefore, since $\mbox{\small\rm NEXP}\subset\mbox{\rm P}/\mbox{\rm poly}$ there is a polynomial-size boolean circuit $C$ that accepts the vector $(d_{1},\cdots,d_{n})$ iff $x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}$ is a nonzero monomial in the given polynomial (as required for application of Hypothesis 3).

Now, we invoke the derandomization Hypothesis 3. We can apply the Klivans-Spielman polynomial identity test, explained above, to the arithmetic circuit $\hat{C}$ for each of the $t$ weight vectors $w_{1},\cdots,w_{t}$ generated by algorithm $\mathcal{A}_{3}$ to obtain a subexponential deterministic identity test for the circuit $\hat{C}$ by the properties of $\mathcal{A}_{3}$. Now, following the argument of Impagliazzo-Kabanets [KI03] it is easy to derive that the integer Permanent does not have polynomial size arithmetic circuits.

We formulate a stronger version of Hypothesis 3 to obtain a conclusion similar to Theorem 5.2 for commutative circuits. For example we can formulate the hypothesis:

There is a deterministic algorithm $\mathcal{A}_{4}$ that takes as input $(m,n,K)$ and outputs a collection of weight functions $w_{1},w_{2},\cdots,w_{t}$ such that $w_{i}:[n]\rightarrow[2n]$, with the property that for each size $m$, $n$-input oracle boolean circuit $C^{A}$ (where $A$ is EXP-complete) that takes as input $(\alpha_{1},\cdots,\alpha_{n})$ such that $\alpha_{i}\in\{0,\cdots,K\}$, there is some weight vector $w_{i}$ for which there is a unique linear form $(\alpha_{1},\cdots,\alpha_{n})$ accepted by $C^{A}$ which attains the minimum value $\sum_{j=1}^{n}w_{i}(j)\alpha_{j}$. Furthermore, $\mathcal{A}_{4}$ runs in time polynomial in $m$.

It is easy to see that, similar to Theorem 5.2, as a consequence of this hypothesis there is some explicit polynomial $f(x_{1},\cdots,x_{n})$ (i.e. computable in EXP) which does not have commutative circuits of subexponential size.

Discussion

An interesting open question is whether derandomizing similar restricted versions of the Valiant-Vazirani lemma also implies circuit lower bounds. We recall the Valiant-Vazirani lemma as stated in the original paper [VV86].

Let $S\subseteq\{0,1\}^{t}$. Suppose $w_{i},1\leq i\leq t$ are picked uniformly at random from $\{0,1\}^{t}$. For each $i$, let $S_{i}=\{v\in S\mid v.w_{j}=0,1\leq j\leq i\}$ and let $p_{t}(S)$ be the probability that $|S_{i}|=1$ for some $i$. Then $p_{t}(S)\geq 1/4$.

Analogous to our discussion in Section 1, here too we can consider the restricted version where we consider $S_{C}\subseteq\{0,1\}^{n}$ to be the set of $n$-bit vectors accepted by a boolean circuit $C$ of size $m$. We can similarly formulate derandomization hypotheses similar to Hypotheses 1 and 2.

Acknowledgements. We are grateful to Manindra Agrawal for interesting discussions and his suggestion that Theorem 5.2 can be obtained from the stronger hypothesis. We also thank Srikanth Srinivasan for discussions.

References