Algebraic Pseudorandomness in ${\text{VNC}}^0$

Algebraic complexity is a vibrant subarea of complexity theory that studies computation of polynomial and rational functions using basic arithmetic operations. Like boolean complexity theory, algebraic complexity enjoys a rich theory of pseudorandomness, with the polynomial identity testing (PIT) problem playing a central role. The input to the PIT problem is an arithmetic circuit, and the goal is to decide whether the circuit computes the identically zero polynomial. This problem can be efficiently solved with randomness using the Schwartz–Zippel lemma [43, 47], which says that if a degree-$d$ polynomial $f$ is nonzero, then with probability at least $1/2$ a randomly-chosen point from a grid of side-length $2d$ will lead to a nonzero evaluation of $f$. A great deal of work has gone into designing efficient deterministic algorithms for polynomial identity testing, leading to beautiful constructions and connections to other areas of computer science and mathematics.

Algorithms for PIT are often designed by constructing hitting set generators, which play a role analogous to pseudorandom generators in boolean complexity. For a complexity class $𝒞$, a hitting set generator $𝒢$ for $𝒞$ is a (family of) polynomial map(s) $𝒢:{𝔽}^{\mathrm{\ell }}\to {𝔽}^n$ such that for every polynomial $f\in 𝒞$, we have $f=0$ if and only if $f\circ 𝒢=0$.¹¹1Formally, we consider families of polynomials $(f_1,f_2,\mathrm{\dots })$ and families of polynomial maps $({𝒢}_1,{𝒢}_2,\mathrm{\dots })$, rather than a single polynomial $f$ and a single map $𝒢$. We will gloss over this distinction throughout the introduction for the sake of readability, focusing instead on single elements $f_n$ and ${𝒢}_n$ of the respective families. Conceptually, one can think of a generator as mapping $\mathrm{\ell }$ truly random field elements to $n$ pseudorandom field elements. If the generator $𝒢$ can be implemented by an efficient algorithm, then we are led to an improved deterministic PIT algorithm for $𝒞$-circuits: given a circuit $C$, test the composition $C\circ 𝒢$ by brute force. The running time of the naïve brute-force algorithm for PIT has an exponential dependence on the number of variables, and the generator $𝒢$ improves this exponent from $n$ to the smaller $\mathrm{\ell }$, a parameter referred to as the seed length of the generator. The usual aim is to construct generators with seed length that is as small as possible, since this is the most important parameter for improving the running time of the deterministic algorithm.

Numerous constructions of hitting set generators are known, both conditional and unconditional. In this work, we will be interested in designing hitting set generators for strong circuit classes, at or beyond the frontier of our ability to prove super-polynomial lower bounds for explicit polynomials.²²2For results on polynomial identity testing for weaker circuit classes, we refer the reader to the recent survey of Dutta and Ghosh [13], as well as the surveys of Saxena [41, 42]. Starting with Kabanets and Impagliazzo [29], who adapted the Nisan–Wigderson [37] generator to the algebraic setting, there has been a successful line of work constructing hitting set generators for strong circuit classes – including general, unrestricted circuits – under hardness assumptions [14, 12, 2, 44, 24]. In fact, some of the lower bounds assumed by these works have since been proven unconditionally, leading to new deterministic algorithms for PIT! Specifically, the super-polynomial lower bounds of Limaye, Srinivasan, and Tavenas [36] against constant-depth arithmetic circuits, combined with the hardness-to-randomness theorem of Chou, Kumar, and Solomon [12], led to the first deterministic sub-exponential time algorithm to test polynomial identities written as constant-depth circuits.

Recently, Chatterjee and Tengse [11] raised a very interesting question about the complexity of hitting set generators. They asked if it is possible to construct a hitting set generator that is computable in some small complexity class $𝒞$, yet appears pseudorandom to a larger complexity class $𝒟⊋𝒞$. This sort of parameter regime is common throughout cryptography, so they termed such a generator a cryptographic hitting set generator. The question of constructing cryptographic hitting set generators is an extremely interesting one, and is the focus of our work. Aside from this question’s inherent interest, one might expect the techniques underlying the construction of a cryptographic hitting set generator to have other applications within algebraic complexity theory. For example, the analogous question of constructing low-complexity pseudorandom generators was answered in a beautiful work of Applebaum, Ishai, and Kushilevitz [5], and the techniques therein have found numerous applications within cryptography and complexity, such as to the recent study of the range avoidance problem [39].

Most known hardness-randomness connections in algebraic complexity cannot hope to produce a hitting set generator that operates in this cryptographic regime of parameters. Almost all generators that come from algebraic hardness-randomness are reconstructive, meaning that their correctness proofs follow a common template. In a reconstructive proof of correctness, the generator $𝒢$ is proven correct by an argument of the following form: suppose some explicit polynomial $f$, such as the $n\times n$ permanent, is hard to compute. Given a nonzero circuit $C$ of size $s$ that satisfies $C\circ 𝒢=0$, there is a reconstruction procedure that modifies $C$ into a circuit $C^{\prime }$ of size $s+t$ that computes the supposedly-hard polynomial $f$. If $s+t\ll \mathrm{size}(f)$, where $\mathrm{size}(f)$ is the complexity of $f$, then we arrive at a contradiction. The upshot of this argument is that if the circuit $C$ is sufficiently small – in particular, when the circuit $C$ is of size $s\ll \mathrm{size}(f)$ – the hardness of $f$ implies that the composition $C\circ 𝒢$ must be nonzero, i.e., that $𝒢$ hits small circuits. The bottleneck in this argument is that the generator $𝒢$ is usually defined using the hard polynomial $f$ (for example, $𝒢$ may be the Nisan–Wigderson generator applied to $f$), so the complexity of $𝒢$ is necessarily bounded from below by $\mathrm{size}(f)$. Because the reconstruction argument only proves that $𝒢$ is pseudorandom against circuits of size $s\ll \mathrm{size}(f)⩽\mathrm{size}(𝒢)$, this proof template is doomed to fail in constructing a cryptographic hitting set generator. To design cryptographic hitting set generators for strong circuit classes, we need to avoid this reconstructive approach.

One instance where the overhead from reconstruction can be avoided is found in the work of Andrews and Forbes [4]. They gave a subexponential-time algorithm to test polynomial identities that are written as constant-depth circuits. The same algorithmic result was already obtained by the previously-mentioned work of Limaye, Srinivasan, and Tavenas [36]. However, these two algorithms differ in the complexity of the hitting set generator underlying the algorithm: the generator of [36] is reconstructive, whereas the generator of [4] provably has smaller complexity than the circuits it hits. Unlike most works in algebraic hardness-randomness, Andrews and Forbes [4] do not design a generator that is based on evaluations of hard functions, but rather design the generator so that its annihilator ideal consists only of hard polynomials. For a generator $𝒢$, its annihilator ideal, denoted by $\mathrm{Ann}(𝒢)$, is the set of all polynomials $f$ such that $f\circ 𝒢=0$. In principle, one could show that a generator hits a circuit class $𝒞$ by showing that all nonzero polynomials in the annihilator ideal are so complex that they lie outside the circuit class $𝒞$. Proving a statement like this is necessary for the proof of correctness of a generator, but these statements are usually not the core thrust of the argument and only arise as a byproduct of the correctness proof. As we will see, adopting this viewpoint will be useful for constructing further examples of generators that hit circuits more complex than the generator itself.

Although the question of constructing cryptographic hitting set generators in algebraic complexity is a recent one, prior work on degree bounds for annihilating polynomials leads, at least implicitly, to constructions of cryptographic generators. Kayal [31, Theorem 12] showed that over a field of characteristic zero, any annihilator of the $n+1$ polynomials

must have degree at least $d^n$. Equivalently, the corresponding generator $𝒢:{𝔽}^n\to {𝔽}^{n+1}$ given by $𝒢(\overline{x})=(g_1(\overline{x}),\mathrm{\dots },g_{n+1}(\overline{x}))$ hits all polynomials of degree less than $d^n$. Because many restricted forms of arithmetic circuits, such as arithmetic formulas and branching programs, necessarily compute low-degree polynomials, this generator hits powerful classes of circuits. For example, size-$s$ arithmetic branching programs cannot compute polynomials of degree greater than $s$, so this generator hits all branching programs of size less than $d^n$. This is a bit unusual. The best-known lower bounds against arithmetic branching programs are only quadratic [10], so intuition from the hardness versus randomness paradigm suggests we should only expect to have constructions of generators that hit branching programs of size up to $O(n^2)$.

The preceding example of Kayal [31] fits into the cryptographic regime, as the outputs are extremely simple to compute. Taking $d=2$, we obtain a generator where the first $n$ outputs can be computed by formulas of constant size, the last output can be computed by a formula of size $n$ and depth two, and yet the generator hits all branching programs of size less than $2^n$. Although this generator only stretches its input by one field element in length, it is possible to improve the stretch of the generator by invoking $n^{1-\epsilon }$ copies in parallel, each on a fresh set of $n^{\epsilon }$ variables. This results in a generator ${𝒢}^{\prime }:{𝔽}^n\to {𝔽}^{n+n^{1-\epsilon }}$ that stretches its input by $n^{1-\epsilon }$ field elements. Kayal’s construction can also be modified to obtain a generator with similar parameters where all outputs are computable by constant-size formulas. To do this, we encode the final output $g_{n+1}$ with additional variables $y_2,\mathrm{\dots },y_{n-1}$ via

Kayal’s lower bound on the degree of the annihilator extends to this variation on his example, so we already have constructions of generators where each output is computable by a formula of constant size, yet the generator itself hits polynomials of much higher complexity.

Not only is the problem of constructing cryptographic hitting set generators interesting in its own right, but it is also closely tied to open problems in algebraic proof complexity. The central goal of propositional proof complexity is to understand the $\mathrm{NP}$ versus $\mathrm{coNP}$ problem via the complexity of the $\mathrm{coNP}$-complete unsatisfiability problem: given a boolean formula $\phi$, accept $\phi$ if and only if $\phi$ is unsatisfiable. The typical setting is to first fix a proof system, and then try to find families of boolean formulas ${({\phi }_n)}_{n\in \mathbb{N}}$ such that any proof ${\pi }_n$ of the unsatisfiability of ${\phi }_n$ requires length that is super-polynomial in $n$. Numerous proof systems based on different areas of mathematics, including logic, algebra, and geometry, have been considered.

Most relevant to our work are proof systems based on algebraic reasoning. Without loss of generality, we may assume that our unsatisfiable boolean formula $\phi$ is in 3CNF form. If $\phi$ is an $n$-variate 3CNF formula with $m$ clauses, there is a translation of $\phi$ to a system $ℱ$ of $n+m$ polynomial equations such that $ℱ$ is satisfiable if and only if $\phi$ is satisfiable. This system $ℱ$ consists of the $n$ boolean axioms $x_i^2-x_i=0$, which force the variables $x_i$ to be $\{0,1\}$-valued, and for each clause of the form $(x_1\oplus b_1)\vee (x_2\oplus b_2)\vee (x_3\oplus b_3)$, the trivariate equation

It is easy to see that any boolean assignment to the $x$ variables satisfies this equation if and only if the same assignment satisfies the corresponding clause $(x_1\oplus b_1)\vee (x_2\oplus b_2)\vee (x_3\oplus b_3)$. Thus, if we want to prove that $\phi$ is unsatisfiable, we can instead try to prove the unsatisfiability of the resulting system of polynomial equations $ℱ$.

How does one prove that a system of polynomial equations is unsatisfiable? The answer comes from Hilbert’s Nullstellensatz. Over an algebraically closed field $𝔽$, the system of equations

is unsatisfiable if and only if there are polynomials $g_1,\mathrm{\dots },g_m\in 𝔽[x_1,\mathrm{\dots },x_n]$ such that

We can take the polynomials $\{g_1,\mathrm{\dots },g_m\}$ to be our proof of unsatisfiability. Our goal, then, is to understand the complexity of the simplest refutation $\{g_1,\mathrm{\dots },g_m\}$ of the system of equations $ℱ$.

The complexity of the proof depends on the choice of proof system. The Nullstellensatz proof system [6, 8] measures the length of the proof by the total number of monomials in the $g_i$. A slightly stronger system is the Polynomial Calculus [38, 27], where we are allowed to write the derivation of $1$ from the $f_i$ in a line-by-line manner, but we still pay for the number of monomials written on every line. Much stronger is the Ideal Proof System (IPS), introduced by Grochow and Pitassi [23], which allows us to write the $g_i$ succinctly as arithmetic circuits. Given that refutations in IPS are written as arithmetic circuits, one would hope that techniques for proving arithmetic circuit lower bounds will eventually lead to lower bounds for the IPS.

This hope has played out successfully in recent years. Forbes, Shpilka, Tzameret, and Wigderson [18] introduced two techniques to infer IPS lower bounds from arithmetic circuit lower bounds, and applied these techniques for restricted circuit classes to conclude unconditional lower bounds. The first technique, known as the functional lower bound method, has been further refined and studied by Govindasamy, Hakoniemi, and Tzameret [20] and Hakoniemi, Limaye, and Tzameret [25]. Here, the hard system of equations $ℱ$ typically consists of boolean axioms together with a sparse polynomial that corresponds to an instance of subset sum, possibly lifted with an appropriate gadget.³³3These hard instances are closely related to the previously-discussed example of Kayal [31] that leads to lower bounds on the degree of annihilating polynomials. This method is capable of proving strong lower bounds; for example, Hakoniemi, Limaye, and Tzameret [25] proved super-polynomial lower bounds on the size of constant-depth IPS refutations for such systems of equations. However, current applications of the functional lower bound method are only able to prove lower bounds against refutations of individual degree $O(\log \log n)$. This is to be expected, as functional lower bounds without the individual degree constraint, even for depth-four arithmetic circuits, would lead to new lower bounds in boolean complexity theory [17].

The second technique introduced by Forbes, Shpilka, Tzameret, and Wigderson [18] is based on hardness of multiples. This method is also capable of proving strong lower bounds: later work by Andrews and Forbes [4] proved super-polynomial lower bounds on the size of constant-depth IPS refutations for a system of equations related to matrix rank. Unlike the functional lower bound method, the lower bounds produced from hardness of multiples do not require the IPS refutation to be of small individual degree. However, the drawback to this method is that in order to prove a lower bound against IPS certificates computed by $𝒞$-circuits, there must be at least one polynomial $f$ in the hard instance $ℱ$ which itself cannot be computed efficiently by $𝒞$-circuits. This limitation is inherent to the method, as the lower bound against IPS is derived from circuit lower bounds for one (or more) of the polynomials in the hard instance $ℱ$.

Strong conditional lower bounds for IPS are also known. Alekseev, Grigoriev, Hirsch, and Tzameret [1] proved super-polynomial lower bounds on the size of constant-free IPS refutations of the binary value principle, a system of equations that asserts a natural number $n$ given in binary is negative. Their lower bound assumes the $\tau$-conjecture of Shub and Smale, which asserts that the straight-line program complexity of computing (a multiple of) the integer $n!$ is bounded from below by ${\log }^{\omega (1)}n$. Santhanam and Tzameret [40] showed that under the assumption $\mathrm{VP}\ne \mathrm{VNP}$, there is a sequence of 3CNF formulas that require IPS refutations of super-polynomial size. One drawback of this result is that the sequence of CNF formulas considered by Santhanam and Tzameret [40] may be satisfiable; if this were the case, then the lower bound becomes trivial, as the soundness of IPS implies that it cannot refute a system of satisfiable equations.

Despite the success so far in bringing techniques from arithmetic circuit complexity to bear on IPS, we still seem far from proving unconditional lower bounds for systems of polynomial equations that encode unsatisfiable 3CNF formulas, even against weak subsystems of IPS. Current applications of the functional lower bound method are limited to proving lower bounds against refutations of low individual degree, and some formulations of the method provably cannot lead to lower bounds for boolean instances [25]. The method of lower bounds for multiples can prove unconditional lower bounds against fragments of IPS with no restrictions on the individual degree of the refutation, but the method requires the hard instance to contain polynomials of large circuit complexity, which precludes its application to systems of equations that encode a 3CNF formula. As a step towards proving IPS lower bounds for such systems, can we prove IPS lower bounds for any system of equations where each polynomial in the system can be described by an arithmetic formula of constant size?

Just as prior work on annihilating polynomials led to simple constructions of cryptographic hitting set generators, existing work on lower bounds for Nullstellensatz degree – in particular, examples demonstrating the tightness of these bounds – easily leads to families of simple polynomials that are hard for fragments of IPS. Recall that the Nullstellensatz says that if $f_1=\mathrm{\cdots }=f_m=0$ is an unsatisfiable system of equations, then there are polynomials $g_1,\mathrm{\dots },g_m$ such that ${\sum }_{i=1}^m{f}_i{g}_i=1$. Of particular relevance to our work are degree bounds for the Nullstellensatz: given the polynomials $f_i$, what is the smallest possible degree of the polynomials $g_i$ that witness the identity ${\sum }_{i=1}^n{f}_i{g}_i=1$? A long line of work [26, 7, 9, 32, 15, 45, 33, 28] has established various bounds on the degrees and heights of such polynomials. For example, we know that such polynomials $g_i$ can always be found with degree $\mathrm{deg}(g_i)⩽d^n$, where $d={\max }_i\mathrm{deg}(f_i)$ is the maximum degree of the $f_i$. An example due to Masser and Philippon (see [7]) shows that bounds of this shape are tight. In particular, if we take

then in any expression ${\sum }_{i=1}^n{f}_i{g}_i=1$, the polynomial $g_1$ must satisfy $\mathrm{deg}(g_1)⩾d^n-d^{n-1}$. This degree lower bound implies similar lower bounds on the size of IPS refutations of the above system when the refutation is written as an arithmetic formula or arithmetic branching program. The lower bound follows from the fact that an arithmetic formula or branching program of size $s$ can only compute polynomials of degree at most $s$, so no formula or branching program of size less than $d^n-d^{n-1}$ can compute a refutation of this system.

At first glance, it appears that we have made progress towards IPS lower bounds for refuting 3CNF formulas. The example of Masser and Philippon above gives us a system of polynomial equations, each of which can be encoded by a constant-size arithmetic formula, that requires large refutations in powerful subsystems of IPS. Unfortunately, this line of reasoning cannot lead to IPS lower bounds for systems of polynomials that encode 3CNF formulas. An unsatisfiable 3CNF formula on $n$ variables always admits a degree-$O(n)$ refutation [23], so degree bounds will not result in new lower bounds on the complexity of refuting 3CNF formulas. To make progress towards proving lower bounds for IPS refutations of 3CNF formulas, we need techniques rooted in finer complexity measures than degree.

We now describe our results. As we have seen in Sections 1.2 and 1.4, prior work on degree bounds can be used to construct cryptographic hitting set generators and hard instances for the Ideal Proof System. The main contribution of our work is a new construction of cryptographic hitting set generators whose correctness is based on arithmetic circuit lower bounds, not degree lower bounds. As a corollary, we will obtain families of simple polynomials that are hard to refute in subsystems of the the Geometric Ideal Proof System, itself a restricted form of the Ideal Proof System [23, Appendix B]. Although the theorem statements below already follow from prior work, the constructions appearing in our proofs do not, and we believe there is value in developing techniques in algebraic pseudorandomness and proof complexity that go beyond degree lower bounds.

Our first result is an explicit construction of a low-complexity hitting set generator that hits ${\mathrm{VAC}}^0$, the class of polynomials computed by constant-depth circuits of polynomial size. Each output of our generator is computable in ${\mathrm{VNC}}^0$, i.e., can be computed by an arithmetic formula of constant size.

Under strong but reasonable hardness assumptions, the same techniques yield ${\mathrm{VNC}}^0$-computable hitting set generators that hit larger circuit classes. Our first conditional construction yields a ${\mathrm{VNC}}^0$-computable generator that hits $\mathrm{VF}$, which corresponds to families of polynomials that are computable by polynomial-size formulas. The correctness of this construction relies on the assumption that the border formula complexity of the determinant is super-polynomial.

Although it is commonly conjectured that the formula complexity of the determinant is $n^{\omega (1)}$, it is less clear whether we should expect the same lower bound to hold for border formulas, as border computation is poorly understood even in very weak settings. Despite this gap in our understanding, we find it conceivable that the determinant does require border formulas of super-polynomial size. The reason for this is that recent progress on arithmetic circuit lower bounds [36, 46, 34, 35, 19, 16] has relied on the use of complexity measures based on matrix rank. Because matrix rank is lower semi-continuous, these lower bounds often directly imply lower bounds on border complexity.⁵⁵5See e.g. [4, Section 6.1] for an explanation of how the lower bound of Limaye, Srinivasan, and Tavenas [36] implies a lower bound on border complexity. It is unclear if these methods will prove lower bounds against arithmetic formulas in the near future, and if they do, the hard polynomial may not be the determinant. However, in light of the recent success of rank-based methods in proving lower bounds, coupled with the fact that many of these lower bounds apply to the determinant, it is not out of the question that when we manage to prove lower bounds against arithmetic formulas, the methods used will be rank-based and will apply to the determinant. In that case, we will have corresponding lower bounds on the border formula complexity of the determinant.

Our second conditional construction produces a ${\mathrm{VNC}}^0$-computable generator that hits polynomials that are computable by polynomial-size arithmetic branching programs, a class commonly known as $\mathrm{VBP}$. This result assumes there is a family of polynomials that can be computed by polynomial-size arithmetic circuits but not by polynomial-size arithmetic branching programs.

As a corollary of our generator constructions, we obtain new lower bounds for subsystems of the Geometric Ideal Proof System of Grochow and Pitassi [23, Appendix B], a restricted form of the Ideal Proof System. An easy observation, already made by Grochow, Kumar, Saks, and Saraf [22], shows that hitting set generators immediately yield hard instances for the Geometric Ideal Proof System. The complexity of the generator upper bounds the complexity of the equations in the hard instance, and the hitting property of the generator is used to infer the lower bound against Geometric IPS. Because we construct ${\mathrm{VNC}}^0$-computable generators against ${\mathrm{VAC}}^0$, we obtain a system of equations where every equation can be written as an arithmetic formula of constant size, but no Geometric IPS refutation can be computed by a circuit of constant depth and polynomial size.

We also prove conditional lower bounds against Geometric IPS refutations computed by arithmetic formulas and arithmetic branching programs. The conditions used to prove these lower bounds are the same ones used to construct ${\mathrm{VNC}}^0$-computable generators that hit arithmetic formulas and arithmetic branching programs, respectively.

Although our hard instances do not correspond to encodings of 3CNF formulas, we view these results as progress towards proving lower bounds for refutations of unsatisfiable boolean formulas. As mentioned in Section 1.4, unsatisfiable 3CNF formulas on $n$ variables can always be refuted in degree $O(n)$, so any method of proving lower bounds on the complexity of refuting 3CNF’s must tolerate the existence of low-degree refutations. In all of our lower bounds for Geometric IPS, the hard systems of equations admit refutations of degree $n^{O(1)}$. To the best of our knowledge, this is the first example of a system of equations where each equation can be expressed by an arithmetic formula of constant size, the system admits low-degree refutations, and the system is provably hard to refute in a nontrivial subsystem of IPS.

Due to space constraints, this extended abstract only presents a high-level overview of our techniques. We refer the reader to the full version of this work [3] for further details.

We obtain our ${\mathrm{VNC}}^0$-computable hitting set generators through a transformation that takes a known hitting set generator $𝒢$ and compiles it into a related generator ${𝒢}^{\prime }$ that has much lower complexity, yet retains the hitting property of $𝒢$. A similar high-level approach was taken by Applebaum, Ishai, and Kushilevitz [5] to obtain ${\mathrm{NC}}^0$-computable one-way functions and pseudorandom generators in the boolean setting. There are some superficial similarities between our work and theirs, since both works obtain the new generator ${𝒢}^{\prime }$ through an encoding of the computation of $𝒢$.

However, one difference between our work and [5] is the set of requirements placed on the high-complexity generator $𝒢$. Applebaum, Ishai, and Kushilevitz [5] require $𝒢$ to be of sufficiently low complexity (say, ${\mathrm{NC}}^1$-computable), but are agnostic to the particular choice of the generator $𝒢$. In contrast, our work does not place a requirement on the complexity of the starting generator, but we are only able to handle generators $𝒢$ that are of the specific form

where $f(\overline{x})$ is a polynomial.

We require the starting generator to be of this form because it provides sufficient algebraic structure to completely analyze the resulting low-complexity generator ${𝒢}^{\prime }$. To every generator $𝒢:{𝔽}^{\mathrm{\ell }}\to {𝔽}^n$, one can associate its annihilator ideal $\mathrm{Ann}(𝒢)$, the set of polynomials $h\in 𝔽[z_1,\mathrm{\dots },z_n]$ such that $h\circ 𝒢=0$, i.e., the composition of $h$ and $𝒢$ results in the identically zero polynomial. To prove that a generator $𝒢$ hits a circuit class $𝒞$, it is both necessary and sufficient to show that every nonzero polynomial in the annihilator $\mathrm{Ann}(𝒢)$ cannot be computed within the resource bounds of $𝒞$.

For some generators, we can completely characterize the ideal $\mathrm{Ann}(𝒢)$, which a useful first step towards proving lower bounds for $\mathrm{Ann}(𝒢)$. In the case where $𝒢$ is of the form $𝒢(\overline{x})=(x_1,\mathrm{\dots },x_n,f(\overline{x}))$, it is easy to show that the annihilator ideal is given by

That is, every annihilator of $𝒢$ is a multiple of the polynomial $z_{n+1}-f(z_1,\mathrm{\dots },z_n)$. Because this ideal is generated by a single polynomial (i.e., is a principal ideal), we can leverage existing techniques on polynomial factorization to prove lower bounds for $\mathrm{Ann}(𝒢)$. The argument proceeds by contradiction: if there is a small $𝒞$-circuit that computes an element of $\mathrm{Ann}(𝒢)$, and if $𝒞$-circuits are polynomially-closed under factorization, then there is a small $𝒞$-circuit for $z_{n+1}-f(z_1,\mathrm{\dots },z_n)$. Thus, if the circuit class $𝒞$ is closed under factorization (as are $\mathrm{VP}$ [30] and $\mathrm{VBP}$ [44]), then to prove lower bounds for $\mathrm{Ann}(𝒢)$, it suffices to prove a lower bound on $f(z_1,\mathrm{\dots },z_n)$. This is a much easier task, since we only have to reason about a single polynomial $f$ and not an arbitrary multiple of $f$. In some cases, the circuit class $𝒞$ is not known to be polynomially-closed under factorization. Despite this, we can still make use of results that show for a specific choice of $f$, lower bounds on the $𝒞$-circuit complexity of $f$ imply lower bounds for all multiples of $f$.

So far, we have seen that it is possible to completely understand generators of the form $𝒢(x_1,\mathrm{\dots },x_n)=(x_1,\mathrm{\dots },x_n,f(\overline{x}))$. On its own, this generator has no hope of producing a generator that is of lower complexity than the circuits it hits, since there is always an annihilator of complexity comparable to $f$.

To obtain a generator of lower complexity, we replace the single output $f(\overline{x})$ by a sequence of $s+1$ outputs that encode a size-$s$ circuit $\mathrm{\Phi }$ that computes $f(\overline{x})$.⁶⁶6This transformation is similar to the reduction of Circuit-SAT to 3CNF-SAT and was recently used by Grochow [21] to study the PIT instances that arise from verification of IPS refutations. For each internal gate of $\mathrm{\Phi }$, we introduce a fresh variable $y_i$, and we include the polynomial

in the output of the generator, where $\odot \in \{+,\times \}$ is the operation labeling the $i$^th gate and the children of the $i$^th gate are gates $j$ and $k$.⁷⁷7If the children of the $i$^th gate are not internal gates, we use a different polynomial, but this is a technical point that does not meaningfully impact the overview here. See [3, Definition 3.1] for the precise definition. We also include $y_s$ as an output so that the generator stretches its $n+s$ inputs to $n+s+1$ outputs. It is clear from the definition that each output of this new generator ${𝒢}^{\prime }$ can be computed by an arithmetic formula of constant size, but it is not obvious why ${𝒢}^{\prime }$ preserves any pseudorandom properties the original generator $𝒢$ had.

To show that ${𝒢}^{\prime }$ is pseudorandom, we follow the approach suggested above: we determine the annihilator ideal $\mathrm{Ann}({𝒢}^{\prime })$ and subsequently prove lower bounds on the complexity of all nonzero polynomials in $\mathrm{Ann}({𝒢}^{\prime })$. As we saw, the annihilator ideal $\mathrm{Ann}(𝒢)$ of the starting generator was generated by $z_{n+1}-f(z_1,\mathrm{\dots },z_n)$, so we could infer lower bounds on $\mathrm{Ann}(𝒢)$ from lower bounds for $f$ and its multiples. For ${𝒢}^{\prime }$, the annihilator ideal $\mathrm{Ann}({𝒢}^{\prime })$ is again principal and is generated by a polynomial of the form

where $g$ is a structured polynomial that should be thought of as an error term for the purposes of this overview. To prove that ${𝒢}^{\prime }$ is pseudorandom, it suffices to prove lower bounds on the complexity of multiples of $h$. Because $h$ is close to $f$, one could hope that lower bounds for multiples of $f$ imply comparable lower bounds for multiples of $h$. This is precisely the route we follow to show that ${𝒢}^{\prime }$ is pseudorandom. By instantiating the construction of ${𝒢}^{\prime }$ with a polynomial $f$ whose multiples are hard for a circuit class $𝒞$ (possibly under hardness assumptions), we obtain a generator that is computable in ${\mathrm{VNC}}^0$ yet hits the much larger class $𝒞$.

In particular, Theorem 1.3 follows by taking $f$ to be a family of polynomials that can be computed by polynomial-size arithmetic circuits, but not by polynomial-size arithmetic branching programs. Because branching programs are closed under factorization [44], the hardness of $f$ against branching programs implies that all multiples of $f$ are likewise hard for branching programs. This ultimately implies that the corresponding generator ${𝒢}^{\prime }$ hits polynomial-size arithmetic branching programs. To prove Theorems 1.1 and 1.2, we take the hard polynomial $f$ to be the determinant. Although low-depth arithmetic circuits and arithmetic formulas are not known to be closed under factorization, Andrews and Forbes [4] showed that multiples of the determinant are essentially as hard as the determinant for both of these circuit classes. We then obtain Theorems 1.1 and 1.2 using known lower bounds on the size of low-depth circuits that compute the determinant [36] and the assumed lower bound on the border formula complexity of the determinant, respectively.

We end this overview with a concrete example of the new generator ${𝒢}^{\prime }$ when the polynomial $f$ is taken to be $f(x_1,x_2)=x_1^2-x_2^2$. This polynomial is too simple to yield a generator with useful pseudorandom properties, but its simplicity allows us to explicitly write down the resulting generator and its annihilator ideal.