Authors Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30
www.theoryofcomputing.org
Near-Optimal Bootstrapping of Hitting
Sets
for Algebraic Models
Mrinal Kumar∗ Ramprasad Saptharishi† Anamay Tengse‡
Received April 16, 2019; Revised August 5, 2021; Published December 31, 2023
Abstract. The Polynomial Identity Lemma (also called the “Schwartz–Zippel
lemma”) states that any nonzero polynomial 𝑓 (𝑥 1 , . . . , 𝑥 𝑛 ) of degree at most 𝑠 will
evaluate to a nonzero value at some point on any grid 𝑆 𝑛 ⊆ 𝔽 𝑛 with |𝑆| > 𝑠. Thus,
there is an explicit hitting set for all 𝑛-variate degree-𝑠, size-𝑠 algebraic circuits of
size (𝑠 + 1)𝑛 .
In this paper, we prove the following results:
A preliminary version of this paper appeared in the Proceedings of the 30th Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA 2019) [20].
∗ Tata Institute of Fundamental Research, Mumbai, India. A part of this work was done during postdoctoral stays
at Simons Institute for the Theory of Computing, Berkeley, USA, Center for Mathematical Sciences and Applications
at Harvard, and while visiting TIFR, Mumbai.
† Tata Institute of Fundamental Research, Mumbai, India. Research supported by the Department of Atomic
Energy, Government of India, under project 12-R&D-TFR-5.01-0500
‡ Reichman University, Herzliya. A major part of this work was done as a student at TIFR, Mumbai, when the
author was supported by a fellowship of the DAE, Govt. of India.
ACM Classification: F.2.1, F.1.3
AMS Classification: 68W30, 68Q87, 68Q06
Key words and phrases: algebraic circuits, polynomial identity testing, derandomization,
hardness-randomness, bootstrapping
© 2023 Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2023.v019a012
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
• Let 𝜖 > 0 be a constant. For a sufficiently large constant 𝑛, and all 𝑠 > 𝑛, if we
have an explicit hitting set of size (𝑠 + 1)𝑛−𝜖 for the class of 𝑛-variate degree-𝑠
polynomials that are computable by algebraic circuits of size 𝑠, then for all large
∗
𝑠, we have an explicit hitting set of size 𝑠 exp(exp(𝑂(log 𝑠))) for 𝑠-variate circuits of
degree 𝑠 and size 𝑠.
That is, if we can obtain a barely non-trivial exponent (a factor-𝑠 Ω(1) improve-
ment) compared to the trivial (𝑠 + 1)𝑛 -size hitting set even for constant-variate
circuits, we can get an almost complete derandomization of PIT.
• The above result holds when “circuits” are replaced by “formulas” or “algebraic
branching programs.”
This extends a recent surprising result of Agrawal, Ghosh and Saxena (STOC
2018, PNAS 2019) who proved the same conclusion for the
class of algebraic circuits,
if the hypothesis provided a hitting set of size at most 𝑠 𝑛 (where 𝛿 > 0 is any
0.5−𝛿
constant). Hence, our work significantly weakens the hypothesis of Agrawal, Ghosh
and Saxena to only require a slightly non-trivial saving over the trivial hitting set,
and also presents the first such result for algebraic formulas.
1 Introduction
Multivariate polynomials are the primary protagonists in the field of algebraic complexity and
algebraic circuits form a natural robust model of computation for multivariate polynomials. For
completeness, we now define algebraic circuits : an algebraic circuit is a directed acyclic graph
with internal gates labeled by + (addition) and × (multiplication), and with leaves labeled by
either variables or field constants; computation flows in the natural way.
In the field of algebraic complexity, much of the focus has been restricted to studying
𝑛-variate polynomials whose degree is bounded by a polynomial function in 𝑛, and such
polynomials are called low-degree polynomials. This restriction has several a priori and a posteriori
motivations, and excellent discussions of this can be seen in the thesis of Forbes [12, Section 3.2]
and Grochow’s answer [13] on cstheory.SE. The central question in algebraic complexity is
to find a family of low-degree polynomials that requires large algebraic circuits to compute it.
Despite having made substantial progress in various subclasses of algebraic circuits (see, e. g.,
the surveys [30, 26]), the current best lower bound for general algebraic circuits is merely an
Ω(𝑛 log 𝑑) lower bound of Baur and Strassen [5].
An interesting approach towards proving lower bounds for algebraic circuits is via showing
good upper bounds for the algorithmic task of polynomial identity testing. Our results in this paper
deal with this problem, and we elaborate on this now.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 2
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
1.1 Polynomial Identity Testing
Polynomial identity testing (PIT1) is the algorithmic task of checking if a given algebraic circuit
𝐶 of size 𝑠 computes the identically zero polynomial. As discussed earlier, although a circuit of
size 𝑠 can compute a polynomial of degree 2𝑠 , this question typically deals only with circuits
whose formal degree2 is bounded by the size of the circuit.
PIT is an important algorithmic question in its own right, and many classical results such as the
primality testing algorithm [3], IP = PSPACE [21, 29], algorithms for graph matching [22, 11, 32]
all have polynomial identity tests at their core.
This algorithmic question has two flavors: whitebox PIT and blackbox PIT. Whitebox
polynomial identity tests consist of algorithms that can inspect the circuit (that is, look at the
underlying gate connections etc.) to decide whether the circuit computes the zero polynomial
or not. A stronger algorithm is a blackbox polynomial identity test where the algorithm is only
provided basic parameters of the circuit (such as its size, the number of variables, a bound on the
formal degree) and only has evaluation access to the circuit 𝐶. Hence, a blackbox polynomial
identity test for a class 𝒞 of circuits is essentially just a list of evaluation points 𝐻 ⊆ 𝔽 𝑛 such that
every nonzero circuit 𝐶 ∈ 𝒞 is guaranteed to have some a ∈ 𝐻 such that 𝐶(a) ≠ 0. Such sets of
points are also called hitting sets for 𝒞. Therefore, the running time of a blackbox PIT algorithm
is given by the size of the hitting set, the time taken to generate it given the parameters of the
circuit, and the time taken to evaluate the circuit on these points. We shall say that a hitting set
𝐻 is explicit if there is an algorithm that, given the parameters 𝑛, 𝑑, 𝑠, outputs the set 𝐻 in time
that is polynomial in the bit complexity3 of 𝐻.
The classical Polynomial Identity Lemma4 [25, 9, 33, 28] states the following.
Lemma 1.1 (Polynomial Identity Lemma). Any nonzero polynomial 𝑓 (𝑥 1 , . . . , 𝑥 𝑛 ) of degree at most
𝑑 will evaluate to a nonzero value at a randomly chosen point from a finite grid 𝑆 𝑛 ⊆ 𝔽 𝑛 with probability
𝑑
at least 1 − |𝑆| .
This automatically yields a randomized polynomial-time blackbox PIT algorithm, and also
an explicit hitting set of size (𝑑 + 1)𝑛 , for the class of 𝑛-variate formal degree-𝑑 polynomials.
Furthermore, a simple counting/dimension argument also says that there exist (non-explicit)
poly(𝑠)-size hitting sets for the class of polynomials computed by size-𝑠 algebraic circuits. The
major open question is to find a better deterministic algorithm for this problem, and the task of
constructing deterministic PIT algorithms is intimately connected with the question of proving
explicit lower bounds for algebraic circuits.
Heintz and Schnorr [15], and Agrawal [1] observed that given an explicit hitting set for size-𝑠
circuits, any nonzero polynomial that is designed to vanish on every point of the hitting set
1We use the abbreviation PIT for both the noun ‘polynomial identity test’ and gerund/adjective ‘polynomial
identity testing’. The case would be clear from context.
2This is defined inductively by setting the formal degree of leaves as 1, and taking the sum at every multiplication
gate and the max at every sum gate.
3Throughout the paper, we will only talk about the sizes of the hitting sets as their bit complexities (i. e., the
total bit-lengths) are always bounded by a polynomial in their respective sizes. We provide more details about this
analysis in subsection 4.1.
4A discussion of the history of this result can be found in [6].
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 3
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
cannot be computable by size-𝑠 circuits. By tailoring the number of variables and degree of
the polynomial in this observation, they showed that polynomial-time blackbox PITs yield an
E-computable family { 𝑓𝑛 } of 𝑛-variate multilinear polynomials that require 2Ω(𝑛) -size circuits.
This connection between PIT and lower bounds was strengthened further by Kabanets and
Impagliazzo [18] who showed that explicit families of hard functions can be used to give
non-trivial derandomizations for PIT. Thus, the question of proving explicit lower bounds and
the task of finding upper bounds for PIT are essentially two sides of the same coin.
1.2 Bootstrapping
A recent result of Agrawal, Ghosh and Saxena [2] showed, among other things, the following
surprising blackbox PIT algorithms for size-𝑠 and 𝑛-variate circuits with running time as
result:
bad as 𝑠 𝑛 , where 𝛿 > 0 is a constant, can be used to construct blackbox PIT algorithms
0.5−𝛿
∗
for size-𝑠 circuits with running time 𝑠 exp(exp(𝑂(log 𝑠))) . Note that log∗ 𝑛 refers to the smallest
𝑖 such that the 𝑖-th iterated logarithm log◦𝑖 (𝑛) is at most 1. This shows that good-enough
derandomizations of PIT would be sufficient to get a nearly complete derandomization. Their
proof uses a novel bootstrapping technique where they use the connection between hardness and
derandomization repeatedly so that by starting with a weak hitting set we can obtain better and
better hitting sets.
One of the open questions of Agrawal, Ghosh and Saxena [2] was whether the hypothesis can
be strengthened to a barely non-trivial derandomization. That is, suppose we have a blackbox
PIT algorithm, for the class of 𝑛-variate, size-𝑠 circuits that runs in time 𝑠 𝑜(𝑛) , can we use this to
get a nearly complete derandomization? Note that we have a trivial (𝑠 + 1)𝑛 · poly(𝑠) algorithm
from the Polynomial Identity Lemma (Lemma 1.1). Our main result is an affirmative answer to
this question in a very strong sense. Furthermore, our result holds for typical subclasses that are
reasonably well-behaved under composition. Formally, we prove the following theorem.
Theorem 1.2 (Bootstrapping PIT for algebraic formulas, branching programs and circuits). Let
𝜖 > 0 and 𝑛 ≥ 2 be constants. Suppose that, for all large enough 𝑠, there is an explicit hitting set of
size 𝑠 𝑛−𝜖 for all degree-𝑠, size-𝑠 algebraic formulas (or algebraic branching programs or circuits) over
∗
𝑛 variables. Then, for all large 𝑠, there is an explicit hitting set of size 𝑠 exp(exp(𝑂(log 𝑠))) for the class
of degree-𝑠, size-𝑠 algebraic formulas (or algebraic branching programs or circuits, respectively) over 𝑠
variables.
Remark 1.3. While the hypothesis of Theorem 1.2 above assumes that 𝑛 is a constant, qualitatively
similar results continue to hold even when 𝑛 is slowly growing with 𝑠. For simplicity of notation,
we work with constant 𝑛 throughout the paper and discuss the extension to growing 𝑛 in more
detail in subsection 4.2.
𝑛−𝜖
Note that (𝑠 + 1)𝑛−𝜖 = 𝑠 𝑛−𝜖 · 1 + 1𝑠 < e · 𝑠 𝑛−𝜖 < 𝑠 𝑛−𝜖 for some other constant 𝜖0 > 0 since
0
𝑠 is large enough. Hence, for this theorem, there is no qualitative difference if the hitting set had
size (𝑠 + 1)𝑛−𝜖 instead of 𝑠 𝑛−𝜖 . We also note that as far as we understand, such a statement for
classes such as algebraic formulas, even with the stronger hypothesis of there being an 𝑠 𝑂(𝑛
(1/2)−𝜖 )
,
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 4
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
did not follow from the results in [2]. We elaborate more on this, and the differences between
our proof and theirs in the next subsection.
An interesting, albeit simple corollary of the above result is the following statement.
Corollary 1.4 (From slightly non-trivial PIT to lower bounds). Let 𝜖 > 0 and 𝑘 ≥ 2 be constants.
Suppose that, for all large enough 𝑠, there is an explicit hitting set of size 𝑠 𝑘−𝜖 for all degree-𝑠, size-𝑠
algebraic formulas (or algebraic branching programs or circuits) over 𝑘 variables. Then, for every function
𝑑 : ℕ → ℕ , there is a polynomial family { 𝑓𝑛 }, where 𝑓𝑛 is an 𝑛-variate of degree 𝑑(𝑛), and for every
large enough 𝑛, 𝑓𝑛 cannot be computed by algebraic formulas or algebraic branching programs or circuits
1
of size smaller than 𝑛+𝑑
∗
exp(exp(𝑂(log 𝑛𝑑)))
𝑑 . Moreover, there is an algorithm which when given as input an
𝑛-variate monomial of degree 𝑑, outputs its coefficient in 𝑓𝑛 in deterministic time 𝑛+𝑑
𝑑 .
Thus, a slightly non-trivial blackbox PIT algorithm leads to hard families with near optimal
hardness (as any 𝑛-variate polynomial of total degree 𝑑 trivially has a circuit of size 𝑛+𝑑
𝑑 ). In a
recent result concerning non-commutative algebraic circuits, Carmosino, Impagliazzo, Lovett
and Mihajlin [8] showed that given an explicit polynomial family of constant degree which
requires superlinear size non-commutative circuits, one can obtain explicit polynomial families
of exponential hardness. Besides the obvious differences in the statements, one important point
to note is that the notions of explicitness in the conclusions of the two statements are different
from each other. In [8], the final exponentially hard polynomial family is in VNP provided the
initial polynomial family is also in VNP. On the other hand, for our result, we can say that the
hard polynomial family obtained in the conclusion is explicit in the sense that its coefficients are
computable in deterministic time 𝑛+𝑑
𝑑 . Another difference between Corollary 1.4 and the main
result of [8] is in the hypothesis. From a non-trivial hitting set, we can obtain a large class of
lower bounds by varying parameters appropriately (see Theorem 1.5), however the main result
of [8] starts with a lower bound for a single family. In that regard, our hypothesis appears to be
much stronger and slightly non-standard. We discuss this issue in some detail at the end of the
next section.
In another relevant result, Jansen and Santhanam [17] showed that marginal improvements to
known hitting set constructions imply lower bounds for the permanent polynomial. In particular,
they show that a “sufficiently succinct” hitting set of size 𝑑, for univariates of degree 𝑑 that have
constant-free algebraic circuits of small size, would imply that the permanent polynomial requires
superpolynomial-size constant-free algebraic circuits. Note that even though their hypothesis
needs a much weaker improvement in the size of the hitting set when compared to ours, the
hitting set is additionally required to be “succinct”5, which makes it difficult to compare the two
hypotheses.
1.3 Proof overview
The basic intuition for the proofs in this paper, and as per our understanding also for the proofs
of the results in the work of Agrawal, Ghosh and Saxena [2], comes from the results of Kabanets
5They require their hitting sets to be encoded by uniform TC0 circuits of appropriately small size. See [17] for
details.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 5
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
and Impagliazzo [18], and those of Heintz and Schnorr [15] and Agrawal [1]. We start by
informally stating these results.
Theorem 1.5 (Informal, Heintz and Schnorr [15], Agrawal [1]). Let 𝐻(𝑛, 𝑑, 𝑠) be an explicit hitting
set for circuits of size 𝑠, degree 𝑑 in 𝑛 variables. Then, for every 𝑘 ≤ 𝑛 and 𝑑0 such that 𝑑0 𝑘 ≤ 𝑑 and
(𝑑0 + 1) 𝑘 > |𝐻(𝑛, 𝑑, 𝑠)|, there is a nonzero polynomial in 𝑘 variables and individual degree 𝑑0 that
vanishes on the hitting set 𝐻(𝑛, 𝑑, 𝑠), and hence cannot be computed by a circuit of size 𝑠.
In a nutshell, given an explicit hitting set, we can obtain hard polynomials. In fact, playing
around with the parameters 𝑑0 and 𝑘 ≤ 𝑛, we can get a hard polynomial in 𝑘 variables, of degree
𝑘𝑑0 for all 𝑘, 𝑑0 satisfying 𝑑0 𝑘 < 𝑑 and (𝑑0 + 1) 𝑘 > |𝐻(𝑛, 𝑑, 𝑠)|.
We now state a result of Kabanets and Impagliazzo [18] that shows that hardness can lead to
derandomization.
Theorem 1.6 (Informal, Kabanets and Impagliazzo [18]). A superpolynomial lower bound for
algebraic circuits for an explicit family of polynomials implies a deterministic blackbox PIT algorithm for
𝜖
all algebraic circuits in 𝑛 variables and degree 𝑑 of size poly(𝑛) that runs in time 𝑑 𝑂(𝑛 ) for every 𝜖 > 0.
Now, we move on to the main ideas in our proof. Suppose we have non-trivial hitting sets
for size-𝑠, degree 𝑑 ≤ 𝑠 circuits on 𝑛 variables. The goal is to obtain a blackbox PIT for circuits
of size 𝑠, degree 𝑠 on 𝑠 variables with a much better dependence on the number of variables.
Observe that if the number of variables was much much smaller than 𝑠, say at most a
constant, then the hitting set in the hypothesis has a polynomial dependence on 𝑠, and we are
done. We will proceed by presenting variable reductions to eventually reach this stage. With this
in mind, the hitting sets for 𝑠-variate circuits in the conclusion of Theorem 1.2 are designed
iteratively starting from hitting sets for circuits with very few variables. In each iteration, we
start with a hitting set for size-𝑠, degree 𝑑 ≤ 𝑠 circuits on 𝑛 variables with some dependence
𝛿
on 𝑛 and obtain a hitting set for size-𝑠, degree 𝑑 ≤ 𝑠 circuits on 𝑚 = 2𝑛 variables (for some
𝛿 > 0), that has a much better dependence on 𝑚. Then, we repeat this process till the number of
variables increases up to 𝑠, which takes 𝑂(log∗ 𝑠) iterations. We now briefly outline the steps in
each such iteration.
• Obtaining a family of hard polynomials : The first step is to obtain a family of explicit
hard polynomials from the given hitting sets. This step is done via Theorem 1.5, which
simply uses interpolation to find a nonzero polynomial 𝑄 in 𝑘 variables and degree 𝑑 that
vanishes on the hitting set for size-𝑠 0, degree-𝑑0 circuits on 𝑛 variables, for some 𝑠 0 , 𝑑0 to be
chosen appropriately.
• Variable reduction using 𝑄 : Next we take a combinatorial design (see Definition 2.6)
{𝑆1 , 𝑆2 , . . . , 𝑆𝑚 }, where each 𝑆 𝑖 is a subset of size 𝑘 of a universe of size ℓ = poly(𝑘), and
𝑆 𝑖 ∩ 𝑆 𝑗 𝑘. Consider the map Γ : 𝔽 [𝑥 1 , 𝑥2 , . . . , 𝑥 𝑚 ] → 𝔽 [𝑦1 , 𝑦2 , . . . , 𝑦ℓ ] given by the
substitution Γ(𝐶(𝑥 1 , 𝑥2 , . . . , 𝑥 𝑚 )) = 𝐶 (𝑄(y | 𝑆1 ), 𝑄(y | 𝑆2 ), . . . , 𝑄(y | 𝑆𝑚 )). As Kabanets and
Impagliazzo show in the proof of Theorem 1.6, Γ preserves the nonzeroness of all algebraic
circuits of size 𝑠 on 𝑚 variables, provided 𝑄 is hard enough.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 6
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
We remark that our final argument for this part is slightly simpler than that of Kabanets
and Impagliazzo, and hence our results also hold for algebraic formulas. In particular, we
do not need Kaltofen’s seminal result that algebraic circuits are closed under polynomial
factorization, whereas the proof of Kabanets and Impagliazzo crucially uses Kaltofen’s
result [19]. This comes from the simple, yet effective, observation that if 𝑄 vanishes on
some hitting set, then so does any multiple of 𝑄. This allows us to use the hardness of
low-degree multiples of 𝑄, and so, we do not need any complexity guarantees on factors of
polynomials.
It is worth mentioning that the result of Kabanets and Impagliazzo [18] is the algebraic
analogue of the famous result of Nisan and Wigderson [24] from the boolean world.
However, the algebraic setting allows us to construct polynomials with hardness that is
super-exponential in the number of variables. This is a key reason for bootstrapping to work,
and we shall elaborate a bit more on this later in this section.
• Blackbox PIT for 𝑚-variate circuits of size 𝑠 and degree 𝑠 : We now take the hitting set
given by the hypothesis for the circuit Γ(𝐶) (invoked with appropriate size and degree
parameters) and evaluate Γ(𝐶) on this set. From the discussion so far, we know that if 𝐶 is
nonzero, then Γ(𝐶) cannot be identically zero, and hence it must evaluate to a nonzero
value at some point on this set. The number of variables in Γ(𝐶) is at most ℓ = poly log 𝑚,
whereas its size turns out to be not too much larger than 𝑠. Hence, the size of the hitting set
for 𝐶 obtained via this argument turns out to have a better dependence on the number of
variables 𝑚 than the hitting set in the hypothesis.
To prove Corollary 1.4, we let 𝑡(𝑛) = exp(exp(𝑂(log∗ 𝑛))). Now, we invoke the the conclusion
1 1
of Theorem 1.2 with 𝑠 = 𝑛+𝑑 . Thus, we get an explicit hitting set 𝐻 of size 𝑛+𝑑
10𝑡(𝑛) 10
𝑑 𝑑 for
𝑛-variate circuits of size 𝑠 and degree 𝑑. We now use Theorem 1.5 to get a nonzero polynomial
of degree 𝑑 and 𝑛 which vanishes on the set 𝐻 and hence cannot be computed by circuits of size
at most 𝑠. We skip the rest of the details.
Why does bootstrapping work? As far as we understand, the primary reason that makes
such bootstrapping results feasible is the following observation from the results of Heintz and
Schnorr, and Agrawal [15, 1]: Given a single hitting set, we can obtain a family of lower bounds
by varying the degree and the number of variables in the interpolating polynomial. It turns
out that in the result of Kabanets and Impagliazzo [18] that converts a hard polynomial 𝑃 into
a hitting set, the proof of this conversion has different sensitivities to the degree of 𝑃 and the
number of variables it depends on. The combination of both these facts allows us to start with a
moderately non-trivial hitting set, obtaining a hard polynomial from it of the right degree and
number of variables, and use that to obtain a hitting set which is significantly better than what
we started with. In particular, by choosing a degree that is polynomial in the hitting set size,
say |𝐻 | 0.1 , we can obtain a constant-variate polynomial that vanishes on 𝐻, for any 𝐻. This is
impossible in the boolean world where the best hardness one could hope for is exponential in
the number of variables. This, in our opinion, is a high level picture of why bootstrapping works
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 7
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
in the algebraic world.
Similarities and differences with the proof of Agrawal, Ghosh and Saxena [2]. The high level
outline of our proof is essentially the same as that in [2]. However, there are some differences
that make our final arguments shorter, simpler and more robust than those of Agrawal, Ghosh
and Saxena thus leading to a stronger and near optimal bootstrapping statement in Theorem 1.2.
Moreover, as we already alluded to, our proof extends to formulas and algebraic branching
programs as well, whereas, to the best of our understanding, the proofs in [2] do not. We now
elaborate on the differences.
One of the main differences between the proofs in this paper and those in [2] is in the use
of the result of Kabanets and Impagliazzo [18]. Agrawal, Ghosh and Saxena use this result
as a blackbox to get deterministic PIT using hard polynomials. The result of Kabanets and
Impagliazzo [18] requires a result of Kaltofen, which shows that low-degree algebraic circuits
are closed under polynomial factorization. That is, if a degree-𝑑, 𝑛-variate polynomial 𝑃 has a
circuit of size at most 𝑠, then any factor of 𝑃 has a circuit of size at most (𝑠𝑛𝑑)𝑒 for a constant 𝑒.
Such a closure result is not known to be true for formulas6, and hence the results in [2] do not
seem to extend to these settings. Also, the removal of any dependence on the “factorization
exponent” 𝑒 is a key ingredient in our proof as it allows us to start with a hypothesis of a barely
non-trivial hitting set. To see this more clearly, suppose we wish to start with a hypothesis that
gives hitting sets of size 𝑠 𝑔(𝑛) for 𝑛-variate circuits of size and degree 𝑠. It is then not too difficult
to infer from Lemma 3.2 that for any proof of “variable reduction” using the hybrid argument of
Kabanets and Impagliazzo [18], we require 𝑔(𝑛) to satisfy the relation 𝑒 · 𝑔(𝑛) ≤ 𝑛. This would
mean that 𝑠 𝑔(𝑛) can never be something like 𝑠 𝑛−𝜖 i. e., a poly(𝑠) factor better than the trivial 𝑠 𝑛 .
The other main difference between our proof and that in [2] is rather technical but we try
to briefly describe it. This is in the choice of combinatorial designs. The designs used in this
paper are based on the standard Reed-Solomon code and they yield larger set families than the
designs used by [2]. However, even without these improved design parameters, our proof can
𝛿
be used to provide the same conclusion when starting off with a hitting set of size 𝑠 𝑛 , instead
of the hypothesis of Theorem 1.27.
Also, their proof is quite involved and we are unsure if there are other constraints in their
proof that force such choices of parameters. Our proof, though along almost exactly the
same lines, appears to be more transparent and more malleable with respect to the choice of
parameters.
The strength of the hypothesis. The hypothesis of Theorem 1.2 and also those of the results
in the work of Agrawal, Ghosh and Saxena [2] is that we have a non-trivial explicit hitting set for
algebraic circuits of size 𝑠, degree 𝑑 on 𝑛 variables where 𝑑 and 𝑠 could be arbitrarily large as
functions of 𝑛. This seems like an extremely strong assumption, and also slightly non-standard
6Even for algebraic branching programs such a result was shown only recently (after our work) by Sinhababu and
Thierauf [31].
7Even though 𝑛, 𝜖 and 𝛿 are constants, 𝑛 𝛿 and (𝑛 − 𝜖) are qualitatively different, as 𝜖 is independent of 𝑛.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 8
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
in the following sense. In a typical setting in algebraic complexity, we are interested in PIT for
size-𝑠, degree-𝑑 circuits on 𝑛 variables where 𝑑 and 𝑠 are polynomially bounded in the number
of variables 𝑛. A natural open problem here, which would be a more satisfying statement to
have, would be to show that one can weaken the hypothesis in Theorem 1.2 to only hold for
circuits whose degree and size are both polynomially bounded in 𝑛. It is not clear to us if such a
result can be obtained using the current proof techniques, or is even true.
Having noted that our hypothesis is very strong, and perhaps even slightly unnatural with
respect to the usual choice of parameters in the algebraic setting, we remark that our hypothesis
does in fact follow from the assumptions that the Permanent is hard for Boolean circuits, and the
Generalized Riemann Hypothesis (GRH). The proof is essentially the same as that of Corollary
1 in the work of Jansen and Santhanam [17]. The only difference is that while Jansen and
Santhanam show that there are non-trivial explicit8 hitting sets for univariate polynomials with
small circuits assuming the hardness of Permanent for Boolean circuits and the GRH, here we
have to work with circuits computing multivariate polynomials. At a high level, the proof in [17]
proceeds by constructing a pseudorandom generator for Boolean circuits of appropriate size
assuming the hardness of permanent for Boolean circuits. Then, the set of binary strings in the
output of this generator is interpreted in a natural way as an integer. This gives us a small set of
integer points, which can be constructed deterministically. Then they argue that there is no
constant free algebraic circuit of small size which vanishes on all these integer points. The proof
of this step is by contradiction, where they assume the existence of such a constant free algebraic
circuit to construct a Boolean circuit of small size which is not fooled by the aforementioned
Boolean pseudorandom generator. For algebraic circuits which are not constant free and are
allowed to use arbitrary field constants and hence cannot be efficiently simulated by a Boolean
circuit, they assume the GRH to reduce to the case of constant free circuits in a fairly standard
way. For our setting, we interpret the output of the Boolean pseudorandom generator as not
just a single integer point, but a 𝑘 tuple of integers points. These set of points in ℤ 𝑘 form our
candidate hitting set. The rest of the proof carries over without any changes. We refer the
interested reader to [17] for further details.
Remark 1.7. Throughout the paper, we shall assume that there are suitable b·c’s or d·e’s if
necessary so that certain parameters chosen are integers. We avoid writing this purely for the
sake of readability.
All results in this paper continue to hold for the underlying model of algebraic formulas,
algebraic branching programs or algebraic circuits. In fact, the results also extend to the model
of border of algebraic formulas, algebraic branching programs or algebraic circuits i. e.if there is
a slightly non-trivial hitting set for polynomials in the border of these classes, then our main
theorem gives a highly non-trivial explicit hitting set for these polynomials. Since our proofs
extend as it is to this setting with essentially no changes, we skip the details for this part, and
confine our discussions in the rest of the paper to just standard algebraic formulas.
8In fact their notion of explicitness is stronger than ours.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 9
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
2 Preliminaries
Notation
• For a positive integer 𝑛, we use [𝑛] to denote the set {1, 2, . . . , 𝑛}.
• We use boldface letters such as x[𝑛] to denote a set {𝑥 1 , . . . , 𝑥 𝑛 }. We drop the subscript
whenever the number of elements is clear or irrelevant in the context.
• For a polynomial 𝑓 (𝑥1 , . . . , 𝑥 𝑛 ), we shall say its individual degree is at most 𝑘 to mean that
the exponent of any of the 𝑥 𝑖 ’s in any monomial is at most 𝑘.
We now define some standard notions we work with, and state some of the known results
that we use in this paper.
2.1 Algebraic models of computation
Throughout the paper we would be dealing with some standard algebraic models and we define
them formally for completeness.
Definition 2.1 (Algebraic branching programs (ABPs)). An algebraic branching program in
variables {𝑥1 , 𝑥2 , . . . , 𝑥 𝑛 } over a field 𝔽 is a directed acyclic graph with a designated starting
vertex 𝑠 with in-degree zero, a designated end vertex 𝑡 with out-degree zero, and the edge between
any two vertices labeled by an affine form from 𝔽 [𝑥 1 , 𝑥2 , . . . , 𝑥 𝑛 ]. The polynomial computed by
the ABP is the sum of all weighted paths from 𝑠 to 𝑡, where the weight of a directed path in an
ABP is the product of labels of the edges in the path.
The size of an ABP is defined as the number of edges in the underlying graph.
Definition 2.2 (Algebraic formulas). An algebraic circuit is said to be a formula if the underlying
graph is a tree. The size of a formula is defined as the number of leaves.
The notation 𝒞(𝑛, 𝑑, 𝑠) will be used to denote the class of 𝑛-variate9 polynomials of degree
at most 𝑑 that are computable by formulas of size at most 𝑠.
We will use the following folklore algorithm for computing univariate polynomials, often
attributed to Horner10. We also include a proof for completeness.
Proposition 2.3 (Horner rule). Let 𝑃(𝑥) = 𝑑𝑖=0 𝑝 𝑖 𝑥 𝑖 be a univariate polynomial of degree 𝑑 over any
Í
field 𝔽 . Then, 𝑃 can be computed by an algebraic formula of size 2𝑑 + 1.
Proof. Follows from the fact that 𝑃(𝑥) = (· · · ((𝑝 𝑑 𝑥 + 𝑝 𝑑−1 )𝑥 + 𝑝 𝑑−2 ) · · · )𝑥 + 𝑝 0 , which is a formula
of size 2𝑑 + 1.
9This class may also include polynomials that actually depend on fewer variables but are masquerading as
𝑛-variate polynomials.
10Though this method was discovered at least 800 years earlier by the Iranian mathematician and astronomer
Sharaf al-Dı̄n T.ūsı̄ (see Hogendijk [16]).
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 10
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
The following observation shows that the classes of algebraic formulas/ABPs/circuits are
“robust” under some very natural operations; we shall call such models as natural models. These
properties are precisely the ones that we rely on in this paper. Any natural model would be
sufficient for our purposes but it might be convenient for the reader to focus on just the standard
models of formulas, ABPs and circuits.
Definition 2.4 (Natural algebraic models). An algebraic model 𝒜 is called a natural model if the
class of polynomials computed by it satisfies the following properties.
• Any polynomial of degree 𝑑 with at most 𝑠 monomials has 𝒜-size at most 𝑠 · 𝑑. In the
specific setting when the polynomial is a univariate, its 𝒜-size is 𝑂(𝑑).
• Partial substitution of variables by constants does not increase the 𝒜-size of any polynomial.
• If each of 𝑄1 , . . . , 𝑄 𝑘 is computable in 𝒜-size 𝑠, then 𝑄 𝑖 is computable in 𝒜-size at most
Í
𝑠 𝑘.
• Suppose 𝑃(𝑥 1 , . . . , 𝑥 𝑛 ) is computable in 𝒜-size 𝑠 1 and say 𝑄 1 , . . . , 𝑄 𝑛 are polynomials
each of which can be computed in 𝒜-size 𝑠 2 . Then, 𝑃(𝑄1 , . . . , 𝑄 𝑛 ) can be computed in
𝒜-size at most 𝑠 1 · 𝑠 2 .
Observation 2.5. Algebraic circuits, branching programs (ABPs), and formulas are natural algebraic
models.
2.2 Combinatorial designs
Definition 2.6 (Combinatorial designs (Nisan [23])). A family of sets {𝑆1 , . . . , 𝑆𝑚 } is said to be
an (ℓ , 𝑘, 𝑟) design if
• 𝑆 𝑖 ⊆ [ℓ ],
• |𝑆 𝑖 | = 𝑘,
• 𝑆 𝑖 ∩ 𝑆 𝑗 < 𝑟 for any 𝑖 ≠ 𝑗.
The following is a standard construction of such designs based on the Reed-Solomon code, similar
to the construction described in [24, Lemma 2.5].
Lemma 2.7 (Construction of designs). Let 𝑐 ≥ 2 be any positive integer. There is an algorithm that,
given parameters ℓ , 𝑘, 𝑟 satisfying ℓ = 𝑘 𝑐 and 𝑟 ≤ 𝑘 with 𝑘 being a power of 2, outputs an (ℓ , 𝑘, 𝑟) design
{𝑆1 , . . . , 𝑆𝑚 } for 𝑚 ≤ 𝑘 (𝑐−1)𝑟 in time poly(𝑚).
Proof. Since 𝑘 is a power of 2, we can identify [𝑘] with the field 𝔽 𝑘 of 𝑘-elements and [ℓ ] with
𝔽 𝑘 × 𝔽 𝑘 𝑐−1 . For each univariate polynomial 𝑝(𝑥) ∈ 𝔽 𝑘 𝑐−1 [𝑥] of degree less than 𝑟, define the set 𝑆 𝑝
as
𝑆 𝑝 = {(𝑖, 𝑝(𝑖)) : 𝑖 ∈ 𝔽 𝑘 } .
Since there are 𝑘 (𝑐−1)𝑟 such polynomials we get 𝑘 (𝑐−1)𝑟 subsets of 𝔽 𝑘 × 𝔽 𝑘 𝑐−1 of size 𝑘 each.
Furthermore, since any two distinct univariate polynomials cannot agree at 𝑟 or more places, it
follows that 𝑆 𝑝 ∩ 𝑆 𝑞 < 𝑟 for 𝑝 ≠ 𝑞.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 11
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
2.3 Hardness-randomness connections
Observation 2.8. Let 𝐻 be a hitting set for the class 𝒞(𝑛, 𝑑, 𝑠) of 𝑛-variate polynomials of degree at
most 𝑑 that are computable by formulas of size 𝑠. Then, for any nonzero polynomial 𝑄(𝑥 1 , . . . , 𝑥 𝑛 ) such
that deg(𝑄) ≤ 𝑑 and 𝑄(a) = 0 for all a ∈ 𝐻, we have that 𝑄 cannot be computed by formulas of size 𝑠.
Proof. If 𝑄 was indeed computable by formulas of size at most 𝑠, then 𝑄 is a member of 𝒞(𝑛, 𝑑, 𝑠)
for which 𝐻 is a hitting set. This would violate the assumption that 𝐻 was a hitting set for this
class as 𝑄 is a nonzero polynomial in the class that vanishes on all of 𝐻.
From this observation, it is easy to see that explicit hitting sets can be used to construct lower
bounds.
Lemma 2.9 (Hitting sets to hardness [15, 1]). Let 𝐻 be an explicit hitting set for 𝒞(𝑛, 𝑑, 𝑠). Then, for
any 𝑘 ≤ 𝑛 such that 𝑘|𝐻 | 𝑘 ≤ 𝑑, there is a polynomial 𝑄(𝑧 1 , . . . , 𝑧 𝑘 ) of individual degree smaller than
1
|𝐻 | 𝑘 that is computable in time poly(|𝐻 |) that requires formulas of size 𝑠 to compute it. Furthermore,
1
given the set 𝐻, there is an algorithm to output a formula of size |𝐻 | · 𝑑 for 𝑄 in time poly(|𝐻 |).
Proof. This is achieved by finding a nonzero 𝑘-variate polynomial, for 𝑘 ≤ 𝑛, of individual
degree 𝑑0 < |𝐻 | 𝑘 , that vanishes on the hitting set 𝐻; this can be done by interpreting it as a
1
homogeneous linear system with (𝑑0 + 1) 𝑘 “variables” and at most |𝐻 | “constraints”. Such a 𝑄 𝑘
can then be found via interpolation by solving a system of linear equations in time poly(|𝐻 |).
The degree of 𝑄 𝑘 is at most 𝑘 · |𝐻 | 𝑘 ≤ 𝑑 from the hypothesis and the hardness of 𝑄 𝑘 follows
1
from Observation 2.8.
Remark 2.10 (Bit complexity of 𝑄 𝑘 ). Note that we can obtain a hard polynomial 𝑄 𝑘 such that its
coefficients have bit-lengths that are at most polynomially large in terms of the (total) bit-lengths
of the points in the given hitting set. Moreover, one can also ensure that such a computation only
handles numbers of polynomially larger bit-lengths11, thereby making Lemma 2.9 constructive
in an explicit sense.
It is also known that we can get non-trivial hitting sets from suitable hardness assumptions.
For a fixed (ℓ , 𝑘, 𝑟) design {𝑆1 , . . . , 𝑆𝑚 } and a polynomial 𝑄(𝑧 1 , . . . , 𝑧 𝑘 ) ∈ 𝔽 [z] we shall use the
notation 𝑄Jℓ , 𝑘, 𝑟KNW to denote the vector of polynomials
𝑄Jℓ , 𝑘, 𝑟KNW := (𝑄(y | 𝑆1 ), 𝑄(y | 𝑆2 ), . . . , 𝑄(y | 𝑆𝑚 )) ∈ (𝔽 [𝑦1 , . . . , 𝑦ℓ ])𝑚 .
Kabanets and Impagliazzo [18] showed that, if 𝑄(z[𝑘] ) is hard enough, then 𝑃(𝑄Jℓ , 𝑘, 𝑟KNW )
is nonzero if and only if 𝑃(x[𝑚] ) is nonzero. However, their proof crucially relies on a result of
Kaltofen [19] (or even a non-algorithmic version due to Bürgisser [7]) about the complexity of
factors of polynomials. Hence, this connection is not directly applicable while working with
other subclasses of circuits such as algebraic formulas as we do not know if they are closed
11Edmonds has shown that Gaussian elimination runs in polynomial time in terms of the total bit-length of the
input [10], see [27, Theorem 3.3]. The same effect is achieved by Bareiss’s algorithm [4], a modification of Gaussian
elimination.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 12
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
under factorization. The following lemma can be used in such settings and this paper makes
heavy use of this.
Lemma 2.11 (Hardness to randomness without factor complexity). Let 𝑄(𝑧 1 , . . . , 𝑧 𝑘 ) be an arbitrary
polynomial of individual degree smaller than 𝑑. Suppose there is an (ℓ , 𝑘, 𝑟) design {𝑆1 , . . . , 𝑆𝑚 } and a
nonzero polynomial 𝑃(𝑥 1 , . . . , 𝑥 𝑚 ), of degree at most 𝐷, that is computable by a formula of size at most
𝑠 such that 𝑃(𝑄Jℓ , 𝑘, 𝑟KNW ) ≡ 0. Then there is a polynomial 𝑃(𝑧 ˜ 1 , . . . , 𝑧 𝑘 ), whose degree is at most
𝑘 · 𝑑 · 𝐷 that is divisible by 𝑄 and computable by formulas of size at most 𝑠 · (𝑟 − 1) · 𝑑 𝑟 · (𝐷 + 1).
Moreover, if 𝑟 = 2, then this upper bound can be improved to 4 · 𝑠 · 𝑑 · (𝐷 + 1)
If the polynomial 𝑄(𝑧 1 , . . . , 𝑧 𝑘 ) in the above lemma was chosen such that 𝑄 vanished on some
hitting set 𝐻 for the class of size-𝑠 0, 𝑛-variate, degree 𝑑0 polynomials where 𝑠 0 ≥ 𝑠·(𝑟−1)·𝑑 𝑟 ·(𝐷+1),
then so does 𝑃˜ since 𝑄 divides it. If it happens that deg(𝑃) ˜ ≤ 𝑑0, then Observation 2.8 immediately
yields that 𝑃˜ cannot be computed by formulas of size 𝑠 0, contradicting the conclusion of the
above lemma. Hence, in such instances, we would have that 𝑃(𝑄Jℓ , 𝑘, 𝑟KNW ) . 0, without
appealing to any result about closure of the particular model under factorization.
Proof. Borrowing the ideas from Kabanets and Impagliazzo [18], we look at the 𝑚-variate
substitution (𝑥 1 , . . . , 𝑥 𝑚 ) ↦→ 𝑄Jℓ , 𝑘, 𝑟KNW as a sequence of 𝑚 univariate substitutions. We now
introduce some notation to facilitate this analysis.
Given the (ℓ , 𝑘, 𝑟) design {𝑆1 , . . . , 𝑆𝑚 }, let y𝑖 = y | 𝑆𝑖 , for each 𝑖 ∈ [𝑚]. The tuple 𝑄Jℓ , 𝑘, 𝑟KNW
can therefore be written as (𝑄(y1 ), 𝑄(y2 ), . . . , 𝑄(y𝑚 )) ∈ (𝔽 [𝑦1 , . . . , 𝑦ℓ ])𝑚 . For each 0 ≤ 𝑖 ≤ 𝑚, let
𝑃𝑖 = 𝑃(𝑄(y1 ), 𝑄(y2 ), . . . , 𝑄(y𝑖 ), 𝑥 𝑖+1 , . . . , 𝑥 𝑚 ) ,
which is 𝑃 after substituting for the variables 𝑥 1 , . . . , 𝑥 𝑖 . Since 𝑃0 = 𝑃 is a nonzero polynomial
and 𝑃𝑚 = 𝑃(𝑄Jℓ , 𝑘, 𝑟KNW ) ≡ 0, let 𝑡 be the unique integer with 1 ≤ 𝑡 ≤ 𝑚, for which 𝑃𝑡−1 . 0
and 𝑃𝑡 ≡ 0.
Since 𝑃𝑡 (y, 𝑥 𝑡 , . . . , 𝑥 𝑚 ) is a nonzero polynomial, there exist values that can be substituted to
the variables besides 𝑥 𝑡 and y𝑡 such that it remains nonzero; let this polynomial be 𝑃𝑡0(y𝑡 , 𝑥 𝑡 ).
Also, for each 𝑗 ∈ [𝑡 − 1], let 𝑄 (𝑡) (y 𝑗 ∩ y𝑡 ) be the polynomial obtained from 𝑄(y 𝑗 ) after this
substitution, which is a polynomial of individual degree less than 𝑑 on at most (𝑟 − 1) variables.
We can now make the following observations about 𝑃 0(y𝑡 , 𝑥 𝑡 ):
• Each 𝑄 (𝑡) (y 𝑗 ∩ y𝑡 ) has a formula of size at most (𝑑(𝑟 − 1)) · 𝑑 𝑟−1 , and thus 𝑃 0(y𝑡 , 𝑥 𝑡 ) has a
formula of size at most (𝑠 · (𝑟 − 1) · 𝑑 𝑟 ),
• deg(𝑃 0) ≤ 𝐷 · deg(𝑄) ≤ 𝐷 · (𝑘𝑑), and deg𝑥𝑡 (𝑃 0) ≤ 𝐷,
• 𝑃 0(y𝑡 , 𝑄(y𝑡 )) ≡ 0.
The last observation implies that the polynomial (𝑥 𝑡 − 𝑄(y𝑡 )) divides 𝑃 0. Therefore we can
write 𝑃 0 = (𝑥 𝑡 − 𝑄(y𝑡 )) · 𝑅, for some polynomial 𝑅. Consider 𝑃 0 and 𝑅 as univariates in 𝑥 𝑡 with
coefficients as polynomials in y𝑡 :
𝐷
Õ 𝐷−1
Õ
0
𝑃 = 𝑃𝑖0 · 𝑥 𝑡𝑖 , 𝑅= 𝑅 𝑖 · 𝑥 𝑡𝑖 .
𝑖=0 𝑖=0
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 13
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
If 𝑎 is the smallest index such that 𝑃𝑎0 ≠ 0, then 𝑃𝑎0 = −𝑅 𝑎 · 𝑄(y𝑡 ) and hence 𝑄(y𝑡 ) divides 𝑃𝑎0 .
Any coefficient 𝑃𝑖0 can be obtained from 𝑃 0 using interpolation from (𝐷 + 1) evaluations of 𝑥 𝑡 .
Hence, 𝑃˜ = 𝑃𝑎0 can be computed in size (𝑠 · (𝑟 − 1) · 𝑑 𝑟 · (𝐷 + 1)).
For the case of 𝑟 = 2, observe that the polynomial 𝑄 (𝑡) (y 𝑗 ∩ y𝑡 ) is a univariate of degree at
most 𝑑. Thus, by Proposition 2.3, 𝑄 (𝑡) (y 𝑗 ∩ y𝑡 ) can be computed by a formula of size 2𝑑 + 1 ≤ 4𝑑.
So, we get an upper bound of (4 · 𝑠 · 𝑑) on the formula complexity of 𝑃 0(y𝑡 , 𝑥 𝑡 ) (instead of 𝑂(𝑠𝑑2 )
that we would get by invoking the general bound for 𝑟 = 2) and after interpolation as above, we
get a bound of 4 · 𝑠 · 𝑑 · (𝐷 + 1) on the formula complexity of 𝑃𝑎0 as defined above.
3 Bootstrapping Hitting Sets
The following are the main bootstrapping lemmas to yield our main result. These lemmas
follow the same template as in the proof of Agrawal, Ghosh and Saxena [2] but with some
simple but important new ideas that avoid any requirement on bounds on factor complexity,
and also permitting a result starting from a barely non-trivial hitting set.
Lemma 3.1 (Barely non-trivial to moderately non-trivial hitting sets). Let 𝜖 > 0 and 𝑛 ≥ 2 be
constants. Suppose that for all large enough 𝑠 there is an explicit hitting set of size 𝑠 𝑛−𝜖 , for all degree-𝑠,
size-𝑠 algebraic formulas over 𝑛 variables.
𝑚
Then for a large enough 𝑚 ≥ 𝑛 8 , and for all 𝑠 ≥ 𝑚, there is an explicit hitting set of size 𝑠 50 for all
degree-𝑠, size-𝑠 algebraic formulas over 𝑚 variables.
Lemma 3.2 (Bootstrapping moderately non-trivial hitting sets). Let 𝑛0 be large enough, and 𝑛 be
any power of two that is larger than 𝑛0 . Suppose for all 𝑠 ≥ 𝑛 there are explicit hitting sets of size 𝑠 𝑔(𝑛)
for 𝒞(𝑛, 𝑠, 𝑠), the class of 𝑛-variate degree-𝑠 polynomials computed by size-𝑠 formulas.
𝑛
1. Suppose 𝑔(𝑛) ≤ 50 , then for 𝑚 = 𝑛 10 and all 𝑠 ≥ 𝑚, there are explicit hitting sets of size 𝑠 ℎ(𝑚) for
𝒞(𝑚, 𝑠, 𝑠) where ℎ(𝑚) ≤ · 𝑚4.
1
1
2
1
2. Suppose 𝑔(𝑛) ≤ · 𝑛 4 , then for 𝑚 = 2𝑛 4 and all 𝑠 ≥ 𝑚, there are explicit hitting sets of size
1
1
2
2
𝑠 ℎ(𝑚) for 𝒞(𝑚, 𝑠, 𝑠) where ℎ(𝑚) = 20 · 𝑔(log4 𝑚) .
Furthermore, ℎ(𝑚) also satisfies ℎ(𝑚) ≤ · 𝑚4.
1
1
2
We will defer the proofs of these lemmas to the end of this section and complete the proof of
Theorem 1.2.
Theorem 1.2 (Bootstrapping PIT for algebraic formulas, branching programs and circuits). Let
𝜖 > 0 and 𝑛 ≥ 2 be constants. Suppose that, for all large enough 𝑠, there is an explicit hitting set of
size 𝑠 𝑛−𝜖 for all degree-𝑠, size-𝑠 algebraic formulas (or algebraic branching programs or circuits) over
∗
𝑛 variables. Then, for all large 𝑠, there is an explicit hitting set of size 𝑠 exp(exp(𝑂(log 𝑠))) for the class
of degree-𝑠, size-𝑠 algebraic formulas (or algebraic branching programs or circuits, respectively) over 𝑠
variables.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 14
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
Proof. Notice that Lemma 3.1 and Lemma 3.2 are structured so that the conclusion of Lemma 3.1
is precisely the hypothesis of Lemma 3.2(1), the conclusion of Lemma 3.2(1) is precisely the
hypothesis of Lemma 3.2(2), and Lemma 3.2(2) admits repeated applications as its conclusion
also matches the requirements in the hypothesis. Thus, we can use one application of Lemma 3.1
followed by one application of Lemma 3.2(1) and repeated applications of Lemma 3.2(2) to get
hitting sets for polynomials depending on larger sets of variables, until we can get a hitting set
for the class 𝒞(𝑠, 𝑠, 𝑠).
Let 𝑛0 be large enough so as to satisfy the hypothesis of Lemma 3.1, and the two parts of
Lemma 3.2. We start with an explicit hitting set of size 𝑠 𝑛0 −𝜖 for 𝒞(𝑛0 , 𝑠, 𝑠) and one application
𝑛1
of Lemma 3.1 gives an explicit hitting set of size 𝑠 50 for 𝒞(𝑛1 , 𝑠, 𝑠) for 𝑛1 ≥ 𝑛08 and all 𝑠 ≥ 𝑛1 .
1
Using Lemma 3.2(1) we obtain an explicit hitting set of size 𝑠 (1/10)·𝑚0 for the class 𝒞(𝑚0 , 𝑠, 𝑠) for
4
all 𝑠 ≥ 𝑚0 = 𝑛110 . We are now in a position to apply Lemma 3.2(2) repeatedly. We now set up
some basic notation to facilitate this analysis.
Suppose after 𝑖 applications of Lemma 3.2(2) we have an explicit hitting set for the class
1
𝒞(𝑚 𝑖 , 𝑠, 𝑠) of size 𝑠 𝑡 𝑖 . We wish to track the evolution of 𝑚 𝑖 and 𝑡 𝑖 . Recall that 𝑚 𝑖 = 2𝑚𝑖−1 after
4
one application of Lemma 3.2(2).
Let {𝑏 𝑖 } 𝑖 be such that 𝑏 0 = log 𝑚0 and, for every 𝑖 > 0, let 𝑏 𝑖 = 2(𝑏 𝑖−1 /4) so that 𝑏 𝑖 = log 𝑚 𝑖 .
Similarly to keep track of the complexity of the hitting set, if 𝑠 𝑡 𝑖 is the size of the hitting set for
1
𝒞(𝑚 𝑖 , 𝑠, 𝑠), then by Lemma 3.2(2) we have 𝑡0 = 𝑚04 and 𝑡 𝑖 = 20 · 𝑡 𝑖−1 for all 𝑖 > 0.
1
2
2
The following facts are easy to verify.
• 𝑚 𝑖 ≥ 𝑠 or 𝑏 𝑖 ≥ log 𝑠 for 𝑖 = 𝑂(log∗ 𝑠),
𝑗 𝑗
• for all 𝑗, we have 𝑡 𝑗 = 20(2 −1) · 𝑡02 = exp(exp(𝑂(𝑗))).
• the exponent of 𝑠 in the complexity of the final hitting set is 𝑡 𝑂(log∗ 𝑠) = exp(exp(𝑂(log∗ 𝑠))).
∗
Therefore we have an explicit hitting set of size 𝑠 exp(exp(𝑂(log 𝑠))) for 𝒞(𝑠, 𝑠, 𝑠). An explicit
algorithm describing the hitting set generator is presented in Subsection 4.1.
3.1 Proofs of the bootstrapping lemmas
Here we prove the two main lemmas used in the proof of Theorem 1.2. We restate the lemmas
here for convenience. The proofs follow a very similar template but with different settings of
parameters and minor adjustments.
Lemma 3.3 (Barely non-trivial to moderately non-trivial hitting sets). Let 𝜖 > 0 and 𝑛 ≥ 2 be
constants. Suppose that for all large enough 𝑠 there is an explicit hitting set of size 𝑠 𝑛−𝜖 , for all degree-𝑠,
size-𝑠 algebraic formulas over 𝑛 variables.
𝑚
Then for a large enough 𝑚 ≥ 𝑛 8 , and for all 𝑠 ≥ 𝑚, there is an explicit hitting set of size 𝑠 50 for all
degree-𝑠, size-𝑠 algebraic formulas over 𝑚 variables.
Proof. Let 𝑎 = max(𝑛, 250
𝜖 ). We begin by fixing the design parameters, 𝑘 = 𝑛, ℓ = 𝑎 · 𝑘 = 𝑎 · 𝑛
4 4
and 𝑟 = 2.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 15
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
Constructing a suitably hard polynomial: For 𝐵 = 5𝑘 𝜖 , we construct a polynomial 𝑄 𝑘 (𝑧 1 , . . . , 𝑧 𝑘 )
that vanishes on the hitting set for all size-𝑠 𝐵 degree-𝑠 𝐵 formulas over 𝑘 variables, that has
size 𝑠 𝐵(𝑘−𝜖) using Lemma 2.9. The polynomial 𝑄 𝑘 (z) has the following properties.
• 𝑄 𝑘 has individual degree 𝑑 < 𝑠 𝐵(𝑘−𝜖)/𝑘 , and total degree < 𝑘 · 𝑠 𝐵(𝑘−𝜖)/𝑘 .
• 𝑄 𝑘 is not computable by formulas of size 𝑠 𝐵 .
• 𝑄 𝑘 has a formula of size ≤ (𝑘𝑑) · 𝑠 𝐵(𝑘−𝜖) .
Building the NW design: Using Lemma 2.7, we now construct an (ℓ , 𝑘, 𝑟) design {𝑆1 , . . . , 𝑆𝑚 }
ℓ 𝑟
2
with 𝑚 := 𝑎 𝑘 (4−1) = 𝑎2 𝑘6.
𝑘 =
Variable reduction: Let 𝑃(𝑥 1 , . . . , 𝑥 𝑚 ) be a nonzero 𝑚-variate degree-𝑠 polynomial computable
by a formula of size 𝑠, and let 𝑃(𝑄 𝑘 Jℓ , 𝑘, 𝑟KNW ) ≡ 0. Then, from the ‘moreover’ part of
Lemma 2.11 (since 𝑟 = 2), we get that there is a polynomial 𝑃(𝑧 ˜ 1 , . . . , 𝑧 𝑘 ) that vanishes on
𝐵 𝐵
a hitting set for formulas of size 𝑠 and degree 𝑠 , and is computable by a formula of size
at most
˜ ≤ 4 · 𝑠 · 𝑑 · (𝑠 + 1)
size(𝑃)
≤ 4𝑠(𝑠 + 1) · 𝑠 𝐵(𝑘−𝜖)/𝑘
𝐵(𝑘−𝜖)
≤𝑠 = 𝑠 5+ 𝜖 −5 = 𝑠 𝐵 .
5+ 5𝑘
𝑘
𝐵(𝑘−𝜖)
Moreover, note that the degree of 𝑃(𝑧˜ 1 , . . . , 𝑧 𝑘 ) is at most (𝑘 · 𝑑) · 𝑠 ≤ 𝑠 < 𝑠 𝐵 . Since
2+ 𝑘
𝑃˜ vanishes on the hitting set for formulas of size 𝑠 𝐵 and degree 𝑠 𝐵 , we get a contradiction
due to Observation 2.8. Therefore, it must be the case that 𝑃(𝑄 𝑘 Jℓ , 𝑘, 𝑟KNW ) is nonzero.
Construction of the hitting set: Therefore, starting with a nonzero formula of degree 𝑠, size 𝑠,
over 𝑚 variables, we obtain a nonzero ℓ -variate polynomial of degree at most 𝑠 · (𝑘𝑑) ≤ 𝑠 𝐵 .
At this point we can just use the trivial hitting set given by the Polynomial Identity Lemma
(Lemma 1.1) which has size at most 𝑠 𝐵ℓ .
𝑚
Therefore, what remains to show is that our choice of parameters ensures that 𝐵ℓ < 50 .
𝑚 𝑎2 𝑘6 𝑎𝑘
This is true, as 50 = 50 = 50 · 𝑎 𝑘 5 = 2 · ℓ · 𝑘 > 𝐵ℓ .
1
The construction runs in time that is polynomial in the size of the hitting set in the conclusion,
and the bit-size of the points in it. See Subsection 4.1 for a more elaborate discussion.
Lemma 3.4 (Bootstrapping moderately non-trivial hitting sets). Let 𝑛0 be large enough, and 𝑛 be
any power of two that is larger than 𝑛0 . Suppose for all 𝑠 ≥ 𝑛 there are explicit hitting sets of size 𝑠 𝑔(𝑛)
for 𝒞(𝑛, 𝑠, 𝑠), the class of 𝑛-variate degree-𝑠 polynomials computed by size-𝑠 formulas.
𝑛
1. Suppose 𝑔(𝑛) ≤ 50 , then for 𝑚 = 𝑛 10 and all 𝑠 ≥ 𝑚, there are explicit hitting sets of size 𝑠 ℎ(𝑚) for
𝒞(𝑚, 𝑠, 𝑠) where ℎ(𝑚) ≤ · 𝑚4.
1
1
2
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 16
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
1
2. Suppose 𝑔(𝑛) ≤ · 𝑛 4 , then for 𝑚 = 2𝑛 4 and all 𝑠 ≥ 𝑚, there are explicit hitting sets of size
1
1
2
2
𝑠 ℎ(𝑚) for 𝒞(𝑚, 𝑠, 𝑠) where ℎ(𝑚) = 20 · 𝑔(log4 𝑚) .
Furthermore, ℎ(𝑚) also satisfies ℎ(𝑚) ≤ · 𝑚4.
1
1
2
Proof. The proofs of both parts follow the same template as in the proof of Lemma 3.1 but with
different parameter settings. Hence, we will defer the choices of the parameters ℓ , 𝑘, 𝑟 towards
the end to avoid further repeating the proof. For now, let ℓ , 𝑘, 𝑟 be parameters that satisfy 𝑟 ≤ 𝑘,
ℓ = 𝑘 2 and 5𝑟 · 𝑔(𝑛) ≤ 𝑘.
Constructing a hard polynomial: The first step is to construct a polynomial 𝑄 𝑘 (𝑧 1 , . . . , 𝑧 𝑘 ) that
vanishes on the hitting set for the class 𝒞(𝑛, 𝑠 5 , 𝑠 5 ), where12 𝑘 ≤ 𝑛. This can be done by
using Lemma 2.9. The polynomial 𝑄 𝑘 (z) will therefore have the following properties.
• 𝑄 𝑘 has individual degree 𝑑 smaller than 𝑠 5𝑔(𝑛)/𝑘 , and degree at most 𝑘 · 𝑠 5𝑔(𝑛)/𝑘 .
• Computing 𝑄 𝑘 requires formulas of size more than 𝑠 5 .
• 𝑄 𝑘 has a formula of size at most 𝑠 10𝑔(𝑛) .
Building the NW design: Using the parameters ℓ , 𝑘, 𝑟, and the construction from Lemma 2.7,
we now construct an (ℓ , 𝑘, 𝑟) design {𝑆1 , . . . , 𝑆𝑚 } with 𝑚 ≤ 𝑘 𝑟 .
Variable reduction using 𝑄 𝑘 : Let 𝑃(𝑥 1 , . . . , 𝑥 𝑚 ) ∈ 𝒞(𝑚, 𝑠, 𝑠) be a nonzero polynomial. Suppose
for contradiction that 𝑃(𝑄 𝑘 Jℓ , 𝑘, 𝑟KNW ) ≡ 0, then Lemma 2.11 states that there is a nonzero
˜ 1 , . . . , 𝑧 𝑘 ) of degree at most 𝑠 · 𝑘 · 𝑑 such that 𝑄 𝑘 divides 𝑃,
polynomial 𝑃(𝑧 ˜ and that 𝑃˜ can
be computed by a formula of size at most
𝑠 · (𝑟 − 1) · 𝑑 𝑟 · (𝑠 + 1) ≤ 𝑠 4 · 𝑑 𝑟
≤ 𝑠 4 · 𝑠 5𝑟·𝑔(𝑛)/𝑘
≤ 𝑠5. (since 𝑘, 𝑟 satisfy 5𝑟 · 𝑔(𝑛) ≤ 𝑘)
Furthermore, the degree of 𝑃˜ is at most 𝑠 · 𝑟 · 𝑠 5𝑔(𝑛)/𝑘 ≤ 𝑠 5 . Hence, 𝑃˜ is a polynomial
in 𝑘 ≤ 𝑛 variables, of degree at most 𝑠 5 that vanishes on the hitting set of 𝒞(𝑛, 𝑠 5 , 𝑠 5 )
since 𝑄 𝑘 divides 𝑃. ˜ But then, Observation 2.8 states that 𝑃˜ must require formulas of
size more than 𝑠 5 , contradicting the above size bound. Hence, it must be the case that
𝑃(𝑄 𝑘 Jℓ , 𝑘, 𝑟KNW ) . 0.
Hitting set for 𝒞(𝑚, 𝑠, 𝑠): At this point, we set the parameters 𝑘 and 𝑟 depending on how
quickly 𝑔(𝑛) grows.
𝑛
Part (1) 𝑔(𝑛) ≤ 50 : In this case, we choose 𝑘 = 𝑛 and 𝑟 = 10 (so we satisfy 5𝑟·𝑔(𝑛) ≤ 𝑛 = 𝑘).
From Lemma 2.7, we have an explicit (ℓ , 𝑘, 𝑟) design {𝑆1 , . . . , 𝑆𝑚 } with 𝑚 = 𝑘 𝑟 = 𝑛 10 .
12that is, 𝑄 𝑘 is a 𝑘-variate polynomial that is just masquerading as an 𝑛-variate polynomial that does not depend
on the last 𝑛 − 𝑘 variables.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 17
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
For any nonzero 𝑃 ∈ 𝒞(𝑚, 𝑠, 𝑠), we have that 𝑃(𝑄 𝑘 Jℓ , 𝑘, 𝑟KNW ) is a nonzero ℓ -variate
polynomial of degree at most 𝑠 · 𝑘 · 𝑠 5𝑔(𝑛)/𝑘 ≤ 𝑠 3 . Hence, by just using the trivial hitting
set via the Polynomial Identity Lemma (Lemma 1.1) we have an explicit hitting set of
1
size 𝑠 3ℓ ≤ 𝑠 3𝑚 5 . Since 𝑚 ≥ 𝑛0 and 𝑛0 is large enough, we have that
1
ℎ(𝑚) := 3𝑚 ≤ · 𝑚4.
1 1
5
2
√
Part (2) 𝑔(𝑛) ≤ 𝑛 4 : In this case, we choose 𝑘 = 𝑛 and 𝑟 = 𝑛 4 , so that 5𝑟 · 𝑔(𝑛) ≤
1
1 1
2
10𝑟 · 𝑔(𝑛) ≤ 𝑘 and ℓ = 𝑛. Using Lemma 2.7, we now construct an explicit (ℓ , 𝑘, 𝑟)
1
design {𝑆1 , . . . , 𝑆𝑚 } with 𝑚 = 2𝑛 4 ≤ 𝑘 𝑟 .
We have a formula computing the 𝑛-variate polynomial 𝑃(𝑄 𝑘 Jℓ , 𝑘, 𝑟KNW ) of size at
most 𝑠 · 𝑠 10𝑔(𝑛) ≤ 𝑠 20𝑔(𝑛) =: 𝑠 0. Using the hypothesis for hitting sets for 𝒞(𝑛, 𝑠 0 , 𝑠 0), we
have an explicit hitting set for 𝒞(𝑚, 𝑠, 𝑠) of size at most
(𝑠 0)𝑔(𝑛) = 𝑠 20𝑔(𝑛) = 𝑠 ℎ(𝑚) ,
2
where ℎ(𝑚) = 20 𝑔((log 𝑚)4 ) . Since 𝑛0 is large enough, we have that
2
2
10 · ℎ(𝑚) ≤ 20 · 10 · 𝑔((log 𝑚)4 )
1
≤ 2 log 𝑚 (since 𝑔(𝑛) ≤ 𝑛4)
2 1
2
≤ 𝑚4. (since 𝑚 ≥ 𝑛0 and 𝑛0 is large enough)
1
This completes the proof of both parts of the lemma.
4 Finer analysis of the main result
This section addresses some of the subtle aspects about Theorem 1.2 as follows. First, we
provide an algorithm outlining all the steps in obtaining the final hitting set from the initial one,
which also helps us illustrate the explicitness of all the intermediate hitting sets (including the
corresponding bit complexities). We then discuss how our theorem statement changes if the
hypothesis holds only when the number of variables is a growing function of the size/degree 𝑠.
4.1 Algorithm for generating the hitting set
We now give an algorithm to generate an explicit hitting set for 𝒞(𝑠, 𝑠, 𝑠), for all large 𝑠, using
the hypothesis of Theorem 1.2. Let 𝑛0 be the initial threshold from the hypothesis and let 𝑛1 be
a constant that satisfies the “large enough” requirements of Lemma 3.2.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 18
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
𝑛0 ≥ 2 𝑡0 = (𝑛0 − 𝜖)
𝑛1
𝑛1 is large enough 𝑡1 =
50
1 1
𝑛2 = 𝑛110 𝑡2 = 𝑛24
10
1
For all 𝑖 ≥ 3, 𝑛 𝑖 = 2𝑛 𝑖−1 𝑡 𝑖 := 20𝑡 𝑖−1
4 2
We are provided an algorithm Initial-Hitting-Set(𝑠) that outputs a hitting set for 𝒞(𝑛0 , 𝑠, 𝑠) of
size at most 𝑠 𝑛0 −𝜖 . Algorithm 1 describes a function Hitting-Set which, given inputs 𝑖 and 𝑠,
outputs a hitting set for 𝒞(𝑛 𝑖 , 𝑠, 𝑠) of size at most 𝑠 𝑡 𝑖 in time poly(𝑠 𝑡 𝑖 ).
𝑖 𝑖
From the growth of 𝑛 𝑖 , it follows that 𝑛𝑏 ≥ 𝑠 for 𝑏 = 𝑂(log∗ 𝑠) and 𝑡 𝑖 = 202 −1 𝑡02 . Un-
folding the recursion for Hitting-Set(𝑗, 𝑠), for any 𝑗, the algorithm makes at most 2 𝑗 calls to
Initial-Hitting-Set(𝑠 0) for various sizes 𝑠 0 satisfying
𝑗−1 Î 𝑗−1 𝑡 𝐵𝑡 2𝑗−1
𝑠 0 ≤ 𝑠 𝐵·20 𝑖=1 𝑖 ≤𝑠 = 𝑠 𝑂(𝑡 𝑗 ) .
Thus for Hitting-Set(𝑏, 𝑠), the algorithm makes at most 2𝑏 calls to Initial-Hitting-Set(𝑠 0), for
∗
sizes 𝑠 0 that are at most 𝑠 exp(exp(𝑂(log 𝑠))) . The overall running time is polynomial time in the size
∗
of the final hitting set which is 𝑠 𝑡𝑏 = 𝑠 exp(exp(𝑂(log 𝑠))) .
Bit complexity of the hitting sets. We will now discuss the bit complexity of the hitting sets
that are generated during the bootstrapping procedure. We will analyze Algorithm 1 and
show that any hitting set 𝐻 for 𝑛-variate formulas that the algorithm outputs, will have a bit
complexity that is at most |𝐻 | 𝑓 (𝑛) , for 𝑓 (𝑛) = exp(𝑂(log∗ 𝑛)).
Let us first consider the case when 𝑖 ≥ 3. Suppose each evaluation point in 𝑆0 := 𝐻𝑖−1 (𝑠 5 ) is at
most ℎ 𝑎 bits long, where ℎ = |𝑆0 | and 𝑎 = 𝑓 (𝑛 𝑖−1 ). Using Remark 2.10, we get that each coefficient
of 𝑄 is at most ℎ 𝑐𝑎 bits long, for some other constant 𝑐. The output of Algorithm 1 for this case will
be evaluations of 𝑄 on 𝑆1 := 𝐻𝑖−1 (𝑠 20𝑡 𝑖−1 ). Since |𝑆1 | = ℎ 4𝑡 𝑖−1 , the bit complexity of 𝑆1 is at most
ℎ 4𝑎𝑡 𝑖−1 . Now 𝑄 is a degree < 𝑠 5 polynomial with 𝑂(ℎ) monomials. As a result any evaluation of
𝑄 on a point from 𝑆1 will have at most 𝑂(log ℎ) · ℎ 𝑐𝑎 + 𝑠 5 · ℎ 4𝑎𝑡 𝑖−1 ≤ ℎ 2𝑎·(4𝑡 𝑖−1 ) = |𝑆1 | 2𝑎 , as 𝑡 𝑖−1 is
large enough. Since 𝑛 𝑖 = 2𝑛 𝑖−1 , we have that 𝑓 (𝑛) = exp(𝑂(log∗ 𝑛)). For the cases when 𝑖 = 1 or
1/4
𝑖 = 2, since we use the trivial hitting sets in place of 𝑆1 in the above discussion, the same bounds
will continue to hold.
We want to remark that although the bit complexity of the output of Hitting-Set(𝑖, 𝑠) is
not polynomial in the size 𝑠 𝑡 𝑖 , the exponent 𝑡 𝑖 is always larger than 𝑓 (𝑛 𝑖 ). As a result the time
taken to generate the final hitting set in the conclusion of Theorem 1.2 can still be bounded by
∗
𝑠 exp(exp(𝑂(log 𝑠))) , albeit with a slightly larger constant in 𝑂(log∗ 𝑠).
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 19
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
Algorithm 1: Hitting-Set
Input : Parameter 𝑖 and a size 𝑠.
Output : A hitting set of size 𝑠 𝑡 𝑖 size for 𝒞(𝑛 𝑖 , 𝑠, 𝑠).
1 if 𝑖 = 1 then
Let 𝐴 = max 𝑛0 , 250 𝜖 ,𝐵 = 𝜖
3𝑛0
2
3 Let 𝐻0 (𝑠 𝐵 ) := Initial-Hitting-Set(𝑠 𝐵 ) // size at most 𝑠 𝐵(𝑛0 −𝜖)
4 Compute a nonzero polynomial 𝑄 in 𝑘 = 𝑛0 variables of individual degree smaller
than 𝑠 𝐵𝑡0 /𝑘 that vanishes on 𝐻0 (𝑠 𝐵 ). // takes poly(𝑠 𝐵𝑡0 ) time
5 Compute an (𝐴 · 𝑛0 , 𝑛0 , 2)-design {𝑆1 , . . . , 𝑆𝑛1 } .
4
6 Let 𝑆 ⊆ 𝔽 be of size at least 𝑠 𝐵 .
𝑛1
n o
return (𝑄Jℓ , 𝑘, 𝑟KNW ) (a) : a ∈ 𝑆 𝐴𝑛0 // size at most 𝑠 𝐵𝐴𝑛0 ≤ 𝑠 50 = 𝑠 𝑡1
5 5
7
8 else if 𝑖 = 2 then
9 𝐻1 (𝑠 5 ) := Hitting-Set(1, 𝑠 5 ) // size at most 𝑠 5𝑡1
10 Compute a nonzero polynomial 𝑄 in 𝑘 = 𝑛1 variables of individual degree smaller
than 𝑠 5𝑡1 /𝑘 that vanishes on 𝐻1 (𝑠 5 ). // takes poly(𝑠 5𝑡1 ) time
11 Compute an (𝑛12 , 𝑛1 , 10)-design {𝑆1 , . . . , 𝑆𝑛2 } .
12 Let 𝑆 ⊆ 𝔽 be of size at least 𝑠 3 .
n o 1
return (𝑄Jℓ , 𝑘, 𝑟KNW ) (a) : a ∈ 𝑆 𝑛1 // size at most 𝑠 3𝑛1 ≤ 𝑠 0.1·𝑛2 = 𝑠 𝑡2
2 2 4
13
14 else if 𝑖 ≥ 3 then
15 𝐻𝑖−1 (𝑠 5 ) := Hitting-Set(𝑖 − 1, 𝑠 5 ) // size at most 𝑠 5𝑡 𝑖−1
√
16 Compute a nonzero polynomial 𝑄 in 𝑘 = 𝑛 𝑖−1 variables of individual degree
smaller than 𝑠 5𝑡 𝑖−1 /𝑘 that vanishes on 𝐻𝑖−1 (𝑠 5 ). // takes poly(𝑠 5𝑡 𝑖−1 ) time
√ √4
17 Compute an (𝑛 𝑖−1 , 𝑛 𝑖−1 , 𝑛 𝑖−1 )-design {𝑆1 , . . . , 𝑆𝑛 𝑖 }
𝐻𝑖−1 (𝑠 20𝑡 𝑖−1 ) := Hitting-Set(𝑖 − 1, 𝑠 20𝑡 𝑖−1 ) // size at most 𝑠 20𝑡 𝑖−1
2
18
return (𝑄Jℓ , 𝑘, 𝑟KNW ) (a) : a ∈ 𝐻𝑖−1 (𝑠 20𝑡 𝑖−1 ) // size at most 𝑠 20𝑡 𝑖−1 = 𝑠 𝑡 𝑖
2
19
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 20
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
4.2 Bootstrapping with a slightly weaker hypothesis
We now discuss the analogue of Theorem 1.2 when the number of variables 𝑛 in the hypothesis
grows with the size parameter 𝑠. In particular, the hypothesis now guarantees a hitting set that
is better than the brute force hitting set of size (𝑠 + 1)𝑛 only when 𝑛 grows faster than a certain
function of 𝑠. For example, suppose that for all large 𝑛 and 𝑠, the class 𝒞(𝑛, 𝑠, 𝑠) has hitting sets
𝛿 ◦3 𝛿
of size13 at most 𝑠 𝑛 (log 𝑠) for some small constant 𝛿. Note that this hypothesis is not “helpful”
when 𝑛 is a constant, or even (log◦3 𝑠)𝑜(1) . Nevertheless, we shall show that even this scenario
◦2
allows for a very similar bootstrapping procedure, and leads to hitting sets of size 𝑠 poly(log 𝑠) for
the class 𝒞(𝑠, 𝑠, 𝑠).
We now state the analogue of the “single-step lemma” (Lemma 3.2) that helps us in proving
our main theorem of this section (Theorem 4.2, which is proved at the end of the section).
Lemma 4.1. Let 𝑔, 𝑡 : ℕ → ℕ be non-decreasing functions such that 𝑔(𝑘) ≤ 𝑘 1/4 and 𝑡(𝑥 log 𝑥 ) ≤ 2𝑡(𝑥)
for all 𝑥. Let 1 ≤ 𝑚 ≤ 𝑠 such that
20 · 𝑔 (log 𝑚)4 · 𝑡(𝑠) ≤ log 𝑚. (4.1)
Let (𝑘 1 , 𝑠1 ) = (log 𝑚)4 , 𝑠 5 and (𝑘 2 , 𝑠2 ) = (log 𝑚)4 , 𝑠 100𝑔((log 𝑚) )𝑡(𝑠) . Suppose 𝒞(𝑘 1 , 𝑠1 , 𝑠1 ) and
2
𝑔(𝑘 )𝑡(𝑠 ) 𝑔(𝑘 )𝑡(𝑠 )
𝒞(𝑘 2 , 𝑠2 , 𝑠2 ) have explicit hitting sets of size at most 𝑠 1 1 1 and 𝑠 2 2 2 , respectively.
Then, we have an explicit hitting set for 𝒞(𝑚, 𝑠, 𝑠) of size at most 𝑠 𝑔 (𝑚)𝑡 (𝑠) , where
0 0
2
𝑔 0(𝑚) ≤ 400 · 𝑔 (log 𝑚)4
𝑡 0(𝑠) ≤ 𝑡(𝑠)2 .
Proof. The proof is exactly along similar lines, with just a little more care to set parameters
appropriately.
Fix any 𝑚, 𝑠 that satisfy equation (4.1). Set 𝑟 = log 𝑚, 𝑘 = (log 𝑚)2 and ℓ = (log 𝑚)4 . With
these parameters, equation (4.1) simplifies to 20 · 𝑔(ℓ ) · 𝑡(𝑠) ≤ 𝑟.
Let 𝑆1 , . . . , 𝑆𝑚 be an (ℓ , 𝑘, 𝑟) design, as guaranteed by Lemma 2.7. Let 𝑠 1 = 𝑠 5 . By the
𝑔(ℓ )𝑡(𝑠 )
hypothesis for (𝑘 1 = ℓ , 𝑠1 ) , there is an explicit hitting set 𝐻 of size at most 𝑠 1 1
≤ 𝑠 5𝑔(ℓ )·2·𝑡(𝑠) ≤ 𝑠 𝑟
for 𝒞(𝑘, 𝑠1 , 𝑠1 ). Let 𝑄(𝑧 1 , . . . , 𝑧 𝑘 ) be the explicit polynomial of individual degree at most
𝑠 10𝑔(ℓ )𝑡(𝑠)/𝑘 ≤ 𝑠 𝑟/𝑘 , as guaranteed by Lemma 2.9, that vanishes on the set 𝐻. Therefore, 𝑄 𝑘
satisfies the following properties:
• 𝑄 𝑘 has individual degree less than 𝑠 𝑟/𝑘 and total degree at most 𝑘 · 𝑠 𝑟/𝑘 .
• 𝑄 𝑘 can be computed by formulas of size at most 𝑠 20𝑔(ℓ )𝑡(𝑠) ≤ 𝑠 𝑟 .
Now, suppose 𝑃(𝑥 1 , . . . , 𝑥 𝑚 ) is any nonzero polynomial in 𝒞(𝑚, 𝑠, 𝑠) but 𝑃(𝑄 𝑘 Jℓ , 𝑘, 𝑟KNW ) ≡ 0,
then Lemma 2.11 states that there is a nonzero polynomial 𝑃(𝑧 ˜ 1 , . . . , 𝑧 𝑘 ) such that
13Here log◦𝑖 denotes 𝑖 iterated applications of log, i. e. log◦3 𝑠 = log log log 𝑠.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 21
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
• 𝑃˜ has degree at most 𝑠 3 , and is a multiple of 𝑄 𝑘
• 𝑃˜ is computed by formulas of size at most 𝑠 3 · 𝑠 𝑟 /𝑘 = 𝑠 4
2
However, Observation 2.8 asserts that 𝑃˜ must require formulas of size at least 𝑠 5 and hence it
must be the case that 𝑃(𝑄 𝑘 Jℓ , 𝑘, 𝑟KNW ) . 0.
Let 𝑃 0(𝑧 1 , . . . , 𝑧ℓ ) = 𝑃(𝑄 𝑘 Jℓ , 𝑘, 𝑟KNW ). This is an ℓ -variate nonzero polynomial of degree at
most 𝑠 · deg(𝑄 𝑘 ) ≤ 𝑠 3 and is computable by formulas of size 𝑠 2 = 𝑠 · 𝑠 20𝑔(ℓ )𝑡(𝑠) ≤ 𝑠 20𝑔(ℓ )𝑡(𝑠) . Since
20𝑔(ℓ )𝑡(𝑠) ≤ log 𝑚 ≤ log 𝑠, we have that 𝑡(𝑠 2 ) ≤ 2𝑡(𝑠). Using the hypothesis for (𝑘 2 = ℓ , 𝑠2 ) an
𝑔(ℓ )𝑡(𝑠 2 )
explicit hitting set for 𝒞(ℓ , 𝑠2 , 𝑠2 ) of size at most 𝑠 2 which can be bounded above as follows:
𝑔(ℓ )𝑡(𝑠 2 ) 2·𝑔(ℓ )𝑡(𝑠)
𝑠2 ≤ 𝑠2
≤ 𝑠 20·𝑔(ℓ )𝑡(𝑠)·2·𝑔(ℓ )·𝑡(𝑠)
≤ 𝑠 400·𝑔(ℓ ) ·𝑡(𝑠) ≤ 𝑠 𝑔 (𝑚)𝑡 (𝑠) .
2 2 0 0
Therefore, we have an explicit hitting set for 𝒞(𝑚, 𝑠, 𝑠) of size at most 𝑠 𝑔 (𝑚)𝑡 (𝑠) .
0 0
Intuitively, the above lemma states that if 𝑔(𝑘)𝑡(𝑠) is substantially smaller than 𝑘, then explicit
hitting sets of size 𝑠 𝑔(𝑘)𝑡(𝑠) for 𝒞(𝑘, 𝑠, 𝑠) can be used to obtain an 𝑠 𝑔 (𝑚)𝑡 (𝑠) hitting set for 𝒞(𝑚, 𝑠, 𝑠)
0 0
where 𝑚 is exponentially larger than 𝑘 (if 𝑠 is not too large in comparison to 𝑚). Suppose
𝑔 0(𝑚)𝑡 0(𝑠) is also substantially smaller than 𝑚 (which would roughly translate to 𝑔(𝑘)𝑡(𝑠) being
much smaller than 𝑘; say something like log log 𝑘), then we may be in a position to use the
lemma again to get an even better hitting set.
The following theorem sets up the parameters suitably when we are in a position to use the
above lemma multiple times.
Theorem 4.2. Let 𝑔0 , 𝑡0 : ℕ → ℕ be non-decreasing functions with 𝑔0 (𝑚) ≤ 𝑚 1/4 and 𝑡0 (𝑠) ≤ log 𝑠.
Let 𝑔1 , 𝑔2 , . . . : ℕ → ℕ and 𝑡1 , 𝑡2 , . . . : ℕ → ℕ be defined as 𝑔 𝑖+1 (𝑚) = 400 · 𝑔 𝑖 (log 𝑚)4
2
and
𝑡 𝑖+1 (𝑠) = (𝑡(𝑠)) . Furthermore, let 𝐿0 : ℕ → ℕ as 𝐿1 (𝑥) = (log 𝑥) and 𝐿 𝑖+1 (𝑥) = (𝐿 𝑖 ((log 𝑥) )) for
2 2 4 2
all 𝑖 ≥ 1.
Suppose for every 𝑚, 𝑠 ≥ 1 we have an explicit hitting set for 𝒞(𝑚, 𝑠, 𝑠) of size at most 𝑠 𝑔0 (𝑚)·𝑡0 (𝑠) .
Let 𝑟𝑚,𝑠 ≥ 1 be the largest index such that
• 𝑔 𝑟 (𝑥) ≤ 𝑥 1/4 and 𝑡 𝑟 (𝑥 log 𝑥 ) ≤ 2 · 𝑡 𝑟 (𝑥) for all 𝑥 ≥ 1,
• 100 · 𝑔 𝑟 (𝑚) · 𝑡 𝑟 (𝑠) ≤ 𝐿𝑟 (𝑚).
Then for any 𝑗 ≤ 𝑟𝑚,𝑠 , we have an explicit hitting set for 𝒞(𝑚, 𝑠, 𝑠) of size at most 𝑠 𝑔 𝑗 (𝑚)𝑡 𝑗 (𝑠) .
In particular, 𝒞(𝑠, 𝑠, 𝑠) has an explicit hitting set of size 𝑠 𝐿𝑟 (𝑠) for 𝑟 = 𝑟 𝑠,𝑠 .
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 22
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
Although the above theorem is stated in a general form, it would be instructive to just
consider nice functions of the form 𝑔0 (𝑠) = 𝑠 0.1 . In this case, it can be seen that
𝑂(𝑖)
𝑔 𝑖 (𝑠) = 22 · poly(log◦𝑖 𝑠),
𝑖
𝑡 𝑖 (𝑠) = (log◦3 𝑠)2 , and
𝑂(𝑖)
𝐿 𝑖 (𝑠) = 22 · poly(log◦𝑖 𝑠),
where 𝑔1 (𝑠) 𝐿1 (𝑠) but, certainly for 𝑖 = log∗ 𝑠 we have 𝑔 𝑖 (𝑠) > 𝐿 𝑖 (𝑠). If 𝑡0 is the constant
function, then we are essentially in the same regime as in the previous sections, so we get
𝑟 𝑠,𝑠 = Θ(log∗ 𝑠), and we recover Theorem 1.2. However, if suppose 𝑡0 (𝑠) = log◦3 𝑠 (where log◦𝑖 𝑠
is the iterated logarithm function, i. e. log◦3 𝑠 = log log log 𝑠), then 𝑡3 (𝑠) = (log◦3 𝑠)2 > 𝐿3 (𝑠) and
3
hence 𝑟 𝑠,𝑠 = 2. Nevertheless, the above theorem yields an explicit hitting set of size 𝒞(𝑠, 𝑠, 𝑠) of
◦2
size at most 𝑠 poly log 𝑠 which is still substantially better than 𝑠 𝑔0 (𝑠)𝑡0 (𝑠) > 𝑠 𝑠 .
0.1
Proof. We will prove the theorem by induction on 𝑗. For any 𝑚, 𝑠, the base case of 𝑗 = 0 trivially
satisfied by the hypothesis of the theorem and hence there is nothing to prove.
Inductive step (𝑗 → 𝑗 + 1): Suppose 𝑔 𝑗+1 (𝑥) ≤ 𝑥 1/4 and 𝑡 𝑗+1 (𝑥 log 𝑥 ) ≤ 2 · 𝑡 𝑗+1 (𝑥) for all 𝑥 ≥ 1.
For each 𝑖 ≤ 𝑗 + 1, define 𝒟𝑖 = {(𝑚, 𝑠) : 𝑚 ≤ 𝑠 , 100 · 𝑔 𝑖 (𝑚)𝑡 𝑖 (𝑠) ≤ 𝐿 𝑖 (𝑚)}. By the induction
hypothesis, for every (𝑘, 𝑠 0) ∈ 𝒟 𝑗 we have an explicit hitting set for 𝒞(𝑘, 𝑠 0 , 𝑠 0) of size at most
0
𝑠 0𝑔 𝑗 (𝑘)𝑡 𝑗 (𝑠 ) .
Fix any (𝑚, 𝑠) ∈ 𝒟 𝑗+1 . To construct the explicit hitting set for 𝒞(𝑚, 𝑠, 𝑠), we will use
Lemma 4.1. In order to do that, we need to assert the following claims:
(a) (𝑚, 𝑠) satisfy equation (4.1) (for 𝑔 = 𝑔 𝑗 and 𝑡 = 𝑡 𝑗 ),
𝑔 𝑗 (ℓ )𝑡 𝑗 (𝑠)
(b) 𝒞(ℓ , 𝑠1 , 𝑠1 ), for ℓ = (log 𝑚)4 and 𝑠 = 𝑠 5 , has an explicit hitting set of size at most 𝑠 1 , and
(c) 𝒞(ℓ , 𝑠2 , 𝑠2 ), for ℓ = (log 𝑚)4 and 𝑠 2 = 𝑠 20𝑔 𝑗 (ℓ )𝑡 𝑗 (𝑠) , has an explicit hitting set of size at most
𝑔 𝑗 (ℓ )𝑡 𝑗 (𝑠2 )
𝑠2 .
Pf of Claim (a): (𝑚, 𝑠) ∈ 𝒟 𝑗+1 implies that
𝑔 𝑗+1 (𝑚) 1/2
20 · 𝑔 𝑗 ((log 𝑚) ) · 𝑡 𝑗 (𝑠) = 20 · · 𝑡 𝑗+1 (𝑚)
4
1/2
400
= 𝑔 𝑗+1 (𝑚)𝑡 𝑗+1 (𝑠)
1/2
1
≤ · 𝐿 𝑗+1 (𝑚)1/2 ≤ log 𝑚.
10
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 23
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
Pf of Claim (b): If ℓ = (log 𝑚)4 and 𝑠 1 = 𝑠 5 ,
100 · 𝑔 𝑗 (ℓ )𝑡 𝑗 (𝑠 1 ) ≤ 200 · 𝑔 𝑗 (ℓ )𝑡 𝑗 (𝑠)
= 10 · 𝑔 𝑗+1 (𝑚) · 𝑡 𝑗+1 (𝑠)
1/2
10
≤ · 𝐿 𝑗+1 (𝑚)1/2
10
= 𝐿 𝑗 (ℓ ).
Hence (ℓ , 𝑠1 ) ∈ 𝒟 𝑗 and by the inductive hypothesis, we have an explicit hitting set for 𝒞(ℓ , 𝑠1 , 𝑠1 )
𝑔 𝑗 (ℓ )𝑡 𝑗 (𝑠 1 )
of size at most 𝑠 1 .
Pf of Claim (c): For ℓ = (log 𝑚)4 and 𝑠 2 = 𝑠 20𝑔 𝑗 (ℓ )𝑡 𝑗 (𝑠) , note that Claim (a) shows that 20𝑔 𝑗 (ℓ )𝑡 𝑗 (𝑠) ≤
log 𝑚 ≤ log 𝑠 and hence 𝑡 𝑗 (𝑠 2 ) ≤ 2𝑡 𝑗 (𝑠). Therefore,
100 · 𝑔 𝑗 (ℓ )𝑡 𝑗 (𝑠 2 ) ≤ 200 · 𝑔 𝑗 (ℓ )𝑡 𝑗 (𝑠)
= 10 · 𝑔 𝑗+1 (𝑚) · 𝑡 𝑗+1 (𝑠)
1/2
= 𝐿 𝑗+1 (𝑚) ≤ 𝐿 𝑗 (ℓ ).
1/2
Hence (ℓ , 𝑠2 ) ∈ 𝒟 𝑗 and, by the induction hypothesis, we have an explicit hitting set for 𝒞(ℓ , 𝑠2 , 𝑠2 )
𝑔 𝑗 (ℓ )𝑡 𝑗 (𝑠 2 )
of size at most 𝑠 2 .
Using Lemma 4.1, we have that 𝒞(𝑚, 𝑠, 𝑠) has an explicit hitting set of size 𝑠 𝑔 𝑗+1 (𝑚)𝑡 𝑗+1 (𝑠) .
5 Open problems
We conclude with some open questions.
• A natural question in the spirit of the results in this paper, and those in [2] seems to be the
following: Can we hope to bootstrap lower bounds? In particular, can we hope to start
from a mildly non-trivial lower bound for general algebraic circuits (e. g., superlinear or just
superpolynomial), and hope to amplify it to get a stronger lower bound (superpolynomial
or truly exponential, respectively). In the context of non-commutative algebraic circuits,
Carmosino, Impagliazzo, Lovett and Mihajlin [8] recently showed such results, but no
such result appears to be known for commutative algebraic circuits.
• It would also be interesting to understand if it is possible to bootstrap white box PIT
algorithms. The proofs in this paper strongly rely on the fact that we have a non-trivial
blackbox derandomization of PIT.
• Kabanets and Impagliazzo [18] show that given a polynomial family which requires
exponential-size circuits, there is a blackbox PIT algorithm which runs in quasipolynomial
time (exp(poly(log 𝑛))) on circuits of size poly(𝑛) and degree poly(𝑛), where 𝑛 is the
number of variables. Thus, even with the best hardness possible, the running time of the
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 24
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
PIT algorithm obtained is still no better than quasipolynomially bounded. The question is
to improve this running time to get a better upper bound than that obtained in [18]. In
particular, can we hope to get a deterministic polynomial-time PIT assuming that we have
explicit polynomial families of exponential hardness. This seems to be closely related to
the question about bootstrapping lower bounds.
Since the first version of this paper appeared, there has been some work related to the
problems studied in this paper. Specifically, Guo, Kumar, Saptharishi and Solomon [14] showed
that it is possible to bootstrap even explicit hitting sets of size 𝑠 𝑛 − 1 for 𝑛-variate circuits of
size 𝑠 and degree 𝑠, for a constant 𝑛, to obtain polynomial-time PIT for 𝑠-variate circuits of
size and degree 𝑠. The proof in [14] goes via the direct construction of a hitting set generator
with constant seed length assuming a sufficiently strong hardness assumption, thereby making
progress on the last open question state above as well. One caveat of the results in [14] is that
the underlying field needs to be of sufficiently large characteristic or characteristic zero. Proving
analogous results over fields of small characteristic continues to be a very interesting open
problem.
Acknowledgments: Ramprasad and Anamay would like to thank the organizers of the
Workshop on Algebraic Complexity Theory (WACT 2018) where we first started addressing
this problem. Ramprasad and Anamay would also like to thank Suhail Sherif and Srikanth
Srinivasan for making an observation which led to the strengthening of an older version of this
paper. Mrinal is thankful to Michael Forbes, Josh Grochow and Madhu Sudan for insightful
discussions.
We also thank the anonymous reviewers at Theory of Computing for valuable feedback. The
discussion in subsection 4.2 in particular was a result of a query from one of the reviewers on
whether an analogue of Theorem 1.2 continues to hold when the parameter 𝑛 in the hypothesis
is growing with 𝑠.
Ramprasad and Anamay would also like to acknowledge the support from the Department
of Atomic Energy, Government of India, under project number RTI4001.
References
[1] Manindra Agrawal: Proving lower bounds via pseudo-random generators. In Proc.
25th Found. Softw. Techn. Theoret. Comp. Sci. Conf. (FSTTCS’05), pp. 92–105. Springer, 2005.
[doi:10.1007/11590156_6] 3, 6, 7, 12
[2] Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena: Bootstrapping variables in
algebraic circuits. Proc. Nat. Acad. Sci. USA, 116(17):8107–8118, 2019. Preliminary version in
STOC’18. [doi:10.1073/pnas.1901272116, ECCC:TR18-035] 4, 5, 8, 14, 24
[3] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena: PRIMES is in P. Ann. Math.,
160(2):781–793, 2004. [doi:10.4007/annals.2004.160.781] 3
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 25
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
[4] Erwin H. Bareiss: Sylvester’s identity and multistep integer-preserving Gaussian elimi-
nation. Math. Comput., 22(103):565–578, 1968. [doi:10.1090/S0025-5718-1968-0226829-0]
12
[5] Walter Baur and Volker Strassen: The complexity of partial derivatives. Theoret. Comput.
Sci., 22(3):317–330, 1983. [doi:10.1016/0304-3975(83)90110-X] 2
[6] Anurag Bishnoi, Pete L. Clark, Aditya Potukuchi, and John R. Schmitt: On ze-
ros of a polynomial in a finite grid. Combin. Probab. Comput., 27(3):310–333, 2018.
[doi:10.1017/S0963548317000566] 3
[7] Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory. Volume 7 of
Algorithms and Computation in Mathematics. Springer, 2000. [doi:10.1007/978-3-662-04179-6]
12
[8] Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin: Hardness
amplification for non-commutative arithmetic circuits. In Proc. 33rd Comput. Complexity
Conf. (CCC’18), pp. 12:1–16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.
[doi:10.4230/LIPIcs.CCC.2018.12, ECCC:TR18-095] 5, 24
[9] Richard A. DeMillo and Richard J. Lipton: A probabilistic remark on algebraic program
testing. Inform. Process. Lett., 7(4):193–195, 1978. [doi:10.1016/0020-0190(78)90067-4] 3
[10] Jack Edmonds: Systems of distinct representatives and linear algebra. J. Res. Nat. Bureau of
Standards (B), 71:241–245, 1967. [doi:10.6028/jres.071b.033] 12
[11] Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf: Bipartite perfect match-
ing is in quasi-NC. SIAM J. Comput., 50(3), 2021. Preliminary version in STOC’16.
[doi:10.1137/16M1097870, arXiv:1601.06319, ECCC:TR15-177] 3
[12] Michael A. Forbes: Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching
Programs. Ph. D. thesis, Massachusetts Institute of Technology, 2014. DSpace@MIT. 2
[13] Joshua Grochow: Degree restriction for polynomials in VP, 2013. stackexchange. 2
[14] Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, and Noam Solomon: Derandomization
from algebraic hardness. SIAM J. Comput., 51(2):315–335, 2022. Preliminary version in
FOCS’19. [doi:10.1137/20M1347395] 25
[15] Joos Heintz and Claus-Peter Schnorr: Testing polynomials which are easy to
compute (extended abstract). In Proc. 12th STOC, pp. 262–272. ACM Press, 1980.
[doi:10.1145/800141.804674] 3, 6, 7, 12
[16] Jan P. Hogendijk: Sharaf al-dı̄n T.ūsı̄ on the number of positive roots of cubic equations.
Historia Mathematica, 16(1):69–85, 1989. [doi:10.1016/0315-0860(89)90099-2] 10
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 26
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
[17] Maurice J. Jansen and Rahul Santhanam: Marginal hitting sets imply super-polynomial
lower bounds for permanent. In Proc. 3rd Innovations in Theoret. Comp. Sci. Conf. (ITCS’12),
pp. 496–506. ACM Press, 2012. [doi:10.1145/2090236.2090275, ECCC:TR11-133] 5, 9
[18] Valentine Kabanets and Russell Impagliazzo: Derandomizing polynomial identity tests
means proving circuit lower bounds. Comput. Complexity, 13(1–2):1–46, 2004. Preliminary
version in STOC’03. [doi:10.1007/s00037-004-0182-6, ECCC:TR02-055] 4, 6, 7, 8, 12, 13, 24,
25
[19] Erich Kaltofen: Factorization of polynomials given by straight-line programs. In Silvio
Micali, editor, Randomness and Computation, pp. 375–412. JAI Press, 1989. DSpace@MIT.
Preliminary version in FOCS’85. 7, 12
[20] Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse: Near-optimal bootstrapping
of hitting sets for algebraic circuits. In Proc. 30th Ann. ACM–SIAM Symp. on Discrete
Algorithms (SODA’19), pp. 639–646. SIAM, 2019. [doi:10.1137/1.9781611975482.40] 1
[21] Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan: Algebraic methods
for interactive proof systems. J. ACM, 39(4):859–868, 1990. Preliminary version in FOCS’90.
[doi:10.1145/146585.146605] 3
[22] Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani: Matching is as easy as
matrix inversion. Combinatorica, 7(1):105–113, 1987. Preliminary version in STOC’87.
[doi:10.1007/BF02579206] 3
[23] Noam Nisan: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70,
1991. [doi:10.1007/BF01375474] 11
[24] Noam Nisan and Avi Wigderson: Hardness vs randomness. J. Comput. System Sci.,
49(2):149–167, 1994. [doi:10.1016/S0022-0000(05)80043-1] 7, 11
[25] Øystein Ore: Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter, 1(7):15, 1922. 3
[26] Ramprasad Saptharishi: A survey of lower bounds in arithmetic circuit complexity. Github
survey, 2015. 2
[27] Alexander Schrijver: Theory of Linear and Integer Programming. Wiley–Interscience, 1986.
Wiley. 12
[28] Jacob T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. J.
ACM, 27(4):701–717, 1980. [doi:10.1145/322217.322225] 3
[29] Adi Shamir: IP=PSPACE. J. ACM, 39(4):869–877, 1992. Preliminary version in FOCS’90.
[doi:10.1145/146585.146609] 3
[30] Amir Shpilka and Amir Yehudayoff: Arithmetic circuits: A survey of recent results and open
questions. Found. Trends Theor. Comp. Sci., 5(3–4):207–388, 2010. [doi:10.1561/0400000039] 2
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 27
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
[31] Amit Sinhababu and Thomas Thierauf: Factorization of polynomials given by arithmetic
branching programs. Comput. Complexity, 30(2):15:1–47, 2021. Preliminary version in
CCC’20. [doi:10.1007/s00037-021-00215-0, ECCC:TR20-077] 8
[32] Ola Svensson and Jakub Tarnawski: The matching problem in general graphs is in quasi-
NC. In Proc. 58th FOCS, pp. 696–707. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.70,
arXiv:1704.01929, ECCC:TR17-059] 3
[33] Richard Zippel: Probabilistic algorithms for sparse polynomials. In Proc. Internat. Symp. Sym-
bolic and Algebraic Manipulation (EUROSAM’79), pp. 216–226. Springer, 1979. [doi:10.1007/3-
540-09519-5_73] 3
AUTHORS
Mrinal Kumar
Reader
School of Technology and Computer Science
Tata Institute of Fundamental Research, Mumbai
mrinal tifr res in
https://mrinalkr.bitbucket.io/
Ramprasad Saptharishi
Associate Professor
School of Technology and Computer Science, TIFR, Mumbai
ramprasad tifr res in
https://www.tifr.res.in/~ramprasad/
Anamay Tengse
Postdoctoral Student
Efi Arazi School of Computer Science, Reichman Universiry, Herzliya
anamay tengse gmail com
https://anamay.bitbucket.io/
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 28
N EAR -O PTIMAL B OOTSTRAPPING OF H ITTING S ETS FOR A LGEBRAIC M ODELS
ABOUT THE AUTHORS
Mrinal Kumar is a faculty member in the School of Technology and Computer
Science at the Tata Institute of Fundamental Research (TIFR), Mumbai. Before
moving to TIFR in 2022, he spent a few years as an assistant professor in the
Department of Computer Science and Engineering at IIT Bombay. He is generally
interested in questions in Computational Complexity, Algebraic Complexity and
Coding Theory. He did his Ph. D. at Rutgers, where he was advised by Swastik
Kopparty and Shubhangi Saraf, and spent his postdoctoral years at a convex
combination of Harvard, the Simons Institute and the University of Toronto
before moving to Mumbai in 2019. Much before that, he grew up in the then
small town of Deoghar in the state of Jharkhand in India, and for the first fifteen
years of his life dreamed of growing up to play cricket for a living. His interest in
math was kindled during the course of his interaction with Dr. Jugal Kishore
Singh, his math teacher in high school. Dr. Singh convinced him (and half his
teammates in the cricket team!) that math could be interesting, challenging and
yet accessible. His unconventional lectures were full of delightful anecdotes,
fantastic questions and quite remarkably, even his exams were enjoyable, non-
scary and yet interesting. Perhaps most importantly, he encouraged his students
to think independently, which many of his former students believe is the most
important thing that they ever learnt in school.
Ramprasad Saptharishi is a faculty member in the School of Technology and
Computer Science at the Tata Institute of Fundamental Research, Mumbai, and is
generally interested in most questions of an algebraic nature. He did his Ph. D.
at Chennai Mathematical Institute, advised by Prof. Manindra Agrawal, and
spent a couple of years at Microsoft Research, India and Tel Aviv University for
his postdoc. His other interests include board games, reading ridiculously long
web-series and writing software code. However, writing reasonable biographies
continues to remain outside his area of expertise.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 29
M RINAL K UMAR , R AMPRASAD S APTHARISHI , AND A NAMAY T ENGSE
Anamay Tengse is currently a postdoc at Reichman University in Herzliya, and
was a postdoc at the University of Haifa for a couple of years before that. This
work was done when he was a Ph. D. student in the School of Technology and
Computer Science at TIFR, Mumbai, advised by Ramprasad Saptharishi. Prior
to that, he obtained an M. Tech. from the Department of Computer Science and
Engineering at IIT Bombay, where he first got interested in the theoretical aspects
of computing. His interest in research comes largely from his interactions with
the faculty and his friends from Goa College of Engineering, where he did his
undergrad. He spends a dangerously large chunk of his time indulging in music,
cricket, quizzes on sporcle, trying to understand poetry and linguistics, and
justifying his lack of interest in football (soccer) to people who question his Goan
origin.
T HEORY OF C OMPUTING, Volume 19 (12), 2023, pp. 1–30 30