Authors Chi-Ning Chou, Mrinal Kumar, Noam Solomon,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34
www.theoryofcomputing.org
Closure Results for Polynomial Factorization
Chi-Ning Chou∗ Mrinal Kumar Noam Solomon
Received July 7, 2018; Revised January 30, 2019; Published November 1, 2019
Abstract: In a sequence of fundamental results in the 1980s, Kaltofen (SICOMP 1985,
STOC’86, STOC’87, RANDOM’89) showed that factors of multivariate polynomials with
small arithmetic circuits have small arithmetic circuits. In other words, the complexity class
VP is closed under taking factors. A natural question in this context is to understand if
other natural classes of multivariate polynomials, for instance, arithmetic formulas, algebraic
branching programs, bounded-depth arithmetic circuits or the class VNP, are closed under
taking factors.
In this paper, we show that all factors of degree loga n of polynomials with poly(n)-
size depth-k circuits have poly(n)-size circuits of depth O(k + a). This partially answers
a question of Shpilka–Yehudayoff (Found. Trends in TCS, 2010) and has applications to
hardness–randomness tradeoffs for bounded-depth arithmetic circuits.
As direct applications of our techniques, we also obtain simple proofs of the following
results.
• The complexity class VNP is closed under taking factors. This confirms Conjecture 2.1
in Bürgisser’s monograph (2000) and improves upon a recent result of Dutta, Saxena
and Sinhababu (STOC’18) who showed a quasipolynomial upper bound on the number
of auxiliary variables and the complexity of the verifier circuit of factors of polynomials
in VNP.
A preliminary version of this paper, titled “Hardness vs Randomness for Bounded Depth Arithmetic Circuits,” appeared in
the Proceedings of the 33rd Computational Complexity Conference, 2018.
∗ Supported by Boaz Barak’s NSF awards CCF 1565264 and CNS 1618026.
ACM Classification: F.1.3
AMS Classification: 68Q15, 68Q17
Key words and phrases: algebraic complexity, polynomial factorization circuit lower bounds, Polyno-
mial Identity Testing, Polynomial Identity Lemma
© 2019 Chi-Ning Chou, Mrinal Kumar, and Noam Solomon
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2019.v015a013
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
• A factor of degree d of a polynomial P which can be computed by an arithmetic formula
(or an algebraic branching program) of size s has a formula (an algebraic branching
program, resp.) of size poly(s, d log d , deg(P)). This result was first shown by Dutta et
al. (STOC’18) and we obtain a slightly different proof as an easy consequence of our
techniques.
Our proofs rely on a combination of the ideas, based on Hensel lifting, developed in the
polynomial factoring literature, and the depth-reduction results for arithmetic circuits, and
hold over fields of characteristic zero or of sufficiently large characteristic.
1 Introduction
A fundamental question in computational algebra is the question of polynomial factorization: Given a
polynomial P, can we efficiently compute the factors of P? In this paper, we will be interested in the
following closely related question: Given a structured polynomial P, what can we say about the structure
of factors of P?
In a sequence of seminal papers, Kaltofen [15, 16, 17, 18] showed that if a polynomial P of degree
d in n variables has an arithmetic circuit of size s, then each of its factors has an arithmetic circuit of
size poly(s, n, d). Moreover, he also showed that given the circuit for P, the circuits for its factors can be
computed in time poly(s, n, d) by a randomized algorithm.
Another way of stating this result is that the complexity class VP, which we now define, is uniformly
closed under taking factors.
Definition 1.1 (VP). A family { fn } of polynomials over a field F is said to be in the class VPF if there
exist polynomially bounded functions d, k, v : N → N and a circuit family {gn } such that deg( fn ) ≤ d(n),
size(gn ) ≤ s(n), and fn is computed by gn for every sufficiently large n ∈ N.
We remark that factorization is a fundamental algebraic notion, and so closure under factorization
indicates that a complexity class is algebraically nice in some sense. Thus, it is a natural question to ask
if any of the other naturally and frequently occurring classes of polynomials like VF (polynomials with
small formulas), VBP (polynomials with small algebraic branching programs), bounded-depth arithmetic
circuits, or the class VNP (the algebraic analog of NP or #P) are closed under taking factors.
In recent years, we have had some progress on the question of closure under factorization for bounded-
depth arithmetic circuits (see [8, 29]) or the classes VF, VBP and VNP (see [7]). We will discuss these
results in a later part of this section.
In addition to being basic questions in algebraic complexity, some of these closure results also have
applications to extending the hardness vs. randomness framework of Kabanets and Impagliazzo [13] to
formulas, branching programs or bounded-depth arithmetic circuits. Indeed, Kaltofen’s closure result for
arithmetic circuits is crucial ingredient in the proof of Kabanets and Impagliazzo [13].
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 2
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
1.1 Hardness and randomness
Two of the most basic questions in algebraic complexity theory are the question of proving super-
polynomial lower bounds on the size of arithmetic circuits computing some explicit family of polynomials1
and that of designing efficient deterministic algorithms for Polynomial Identity Testing (PIT).
The progress on these questions for general arithmetic circuits has been painfully slow. To date, there
are no non-trivial algorithms for PIT for general arithmetic circuits, while the best known lower bound on
the circuit size for explicit families of polynomials, due to Bauer and Strassen [3], is a slightly superlinear
lower bound Ω(n log n), proved over three decades ago. In fact, even for the class of bounded-depth
arithmetic circuits, no non-trivial deterministic PIT algorithms are known, and the best circuit lower
bounds known are just slightly superlinear [32].
In a very influential work, Kabanets and Impagliazzo [13] showed that the questions of derandomizing
PIT and that of proving lower bounds for arithmetic circuits are equivalent in some sense. Their result
adapts the Hardness vs. Randomness framework of Nisan and Wigderson [27] to the algebraic setting. In
their proof, Kabanets and Impagliazzo combine the use of the Nisan generator [26] with Kaltofen’s result
that all factors of a low-degree (degree poly(n)) polynomial with a poly(n)-size circuit are computable by
poly(n)-size circuits [18]. They showed that given an explicit family of hard polynomials, one can obtain
a non-trivial2 deterministic algorithm for PIT.
The extremely slow progress on the circuit lower bound and PIT questions for general circuits has
led to a lot of attention on understanding these questions for more structured subclasses of arithmetic
circuits. Arithmetic formula [14], algebraic branching programs [21], multilinear circuits [31, 35, 34],
and bounded-depth arithmetic circuits [28, 32, 11, 10, 23] are some examples of such circuit classes. An
intriguing question is to ask if the equivalence of PIT and lower bounds also carries over to these more
structured circuit classes. For example, do superpolynomial lower bounds for arithmetic formulas imply
non-trivial deterministic algorithms for PIT for arithmetic formulas, and vice versa?
The answers to these questions do not follow directly from the results in [13], and extending the
approach of Kabanets and Impagliazzo to answer these questions seems to be intimately related to the
questions about closure of arithmetic formulas and bounded-depth circuits under polynomial factorization.
We now describe our results, and discuss how they relate to prior work.
2 Results and prior work
2.1 Factors of polynomials with bounded-depth circuits
For our first set of results, we study the bounded-depth circuit complexity of factors of polynomials which
have small bounded-depth circuits. We prove the following result.
Theorem 2.1. Let F be a field of characteristic zero. Let P ∈ F[x] be a polynomial of degree r in n
variables that can be computed by an arithmetic circuit of size s and depth ∆. Let f ∈ F[x] be an
1 Informally, a family { f } of polynomials is said to be explicit, if there is a deterministic algorithm which takes an input an
n
n ∈ N and a monomial and outputs the coefficient of the monomial in fn . Moreover, the time complexity of the algorithm is
polynomially bounded in n and the degree of the monomial. See Section 4.5 for a formal definition.
2 Here, non-trivial means subexponential time, or quasipolynomial time, based on the hardness assumption.
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 3
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
irreducible polynomial of degree d √such that f divides P. Then f can be computed by a circuit of depth
∆ + O(1) and size poly(s, r, n) · d O( d) . Furthermore, for any k ∈ N, f can be computed by a circuit of
1/k
depth ∆ + O(k) and size poly(s, r, n) · d O(d ) .
Thus, low-degree factors of polynomials with small shallow circuits have small shallow circuits. This
partially answers an open problem (Open Problem 19 in [38]) of Shpilka and Yehudayoff who asked
whether the factors of a multivariate polynomial with a small shallow circuit can also be computed by
small shallow circuits.
Our proof gives a smooth tradeoff between the depth of the circuit for the factor and its size. The
tradeoff is governed by the depth-reduction results for arithmetic circuits (see Theorem 4.3). We remark
that the result is also true when the characteristic of the underlying field is sufficiently large. The result
in the literature, which is most closely related to Theorem 2.1, is due to Oliveira [29]. He studied the
question of bounded-depth circuit complexity of factors of polynomials with small bounded-depth circuits,
for polynomials of low individual degree. He showed that if a polynomial P of individual degree r is
computable by a circuit of size s and depth ∆, then every factor of P of degree d can be computed by
a circuit of size poly(s, r, d r ) and depth ∆ + 5. Thus, for polynomials with small individual degree, the
results in [29] are strictly better than ours, whereas for polynomials with unbounded individual degree,
we get a better upper bound on the complexity of factors of total degree poly(log n).
One of our main motivations for studying this question is the connection to hardness-randomness
tradeoffs for bounded-depth arithmetic circuits. In the next section, we describe the implications of our
results in this context.
2.2 Hardness vs. randomness for bounded-depth circuits
Dvir, Shpilka and Yehudayoff [8] initiated the study of the question of the equivalence between PIT
and lower bounds for bounded-depth circuits. Dvir et al. observed that a part of the proof in [13] can
be generalized to show that non-trivial PIT for bounded-depth circuits implies lower bounds for such
circuits. For the converse, the authors only showed a weaker statement; they proved that superpolynomial
lower bounds for depth-∆ arithmetic circuits imply non-trivial PIT for depth-(∆ − 5) arithmetic circuits
with bounded individual degree. The bounded individual degree condition is a bit unsatisfying, and so,
the following question is of interest: Does a superpolynomial lower bound for depth-∆ arithmetic circuits
imply non-trivial deterministic PIT for depth-∆0 arithmetic circuits?3 In particular, can we get rid of the
“bounded individual degree” condition from the results in [8]?
In this paper, we partially answer this question in the affirmative. Here is an informal statement of the
result.
Theorem 2.2 (Informal). A superpolynomial lower bound for depth-∆ arithmetic circuits for an explicit
family of low-degree polynomials implies non-trivial deterministic PIT for depth-(∆ − 5) arithmetic
circuits.
Here, by low-degree polynomials, we mean polynomials in n variables and of degree at most
O(log2 n/ log2 log n). Thus, by strengthening the hardness hypothesis in [8], we remove the bounded
individual degree restriction from the implication. We now state the result in Theorem 2.2 formally.
3 Here, we think of ∆0 as ∆ − O(1).
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 4
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
Theorem 2.3. Let ∆ ≥ 6 be a positive integer, and let ε > 0 be any real number. Let { fm } be an
explicit family of polynomials such that fm is an m-variate multilinear polynomial of degree d =
O log2 m/log2 log m which cannot be computed by an arithmetic circuit of depth ∆ and size poly(m).
Then, there is a deterministic algorithm, which, given as input a circuit C ∈ Q[x] of size s, depth ∆ − 5
2ε
and degree D on n variables, runs in time (snD)O(n ) and determines if the polynomial computed by C is
identically zero.
Some remarks on the above theorem statement.
Remark 2.4. The running time of the PIT algorithm gets better as the lower bound gets stronger. Also,
the constraint on the degree of family of hard polynomials can be further relaxed a bit, at the cost of
strengthening the hardness assumption, and increasing the running time of the resulting PIT algorithm.4
We leave it to the interested reader to work out these details. We also note that the multilinearity
assumption on the family of hard polynomials is without loss of generality.
As discussed earlier, Theorem 2.3 is closely related to the main result in [8]. We now discuss their
similarities and differences.
Comparison with Dvir et al. [8].
• Degree constraint on the hard polynomial. While Theorem 2.3 requires that the hard polynomial
on m variables has degree O(log2 m/ log2 log m), Dvir et al. [8] did not have a similar constraint.
• Individual degree constraint for PIT. In [8], the authors get PIT for shallow circuits with bounded
individual degree, whereas our Theorem 2.3 does not make any assumptions on individual degrees
in this context.
The key technical challenge for extending the known hardness-randomness tradeoffs for general cir-
cuits [13] to restricted circuit classes like formulas or bounded-depth circuits is the following question:
Let P(x, y) ∈ F[x, y] be a polynomial of degree r and let f ∈ F[x] be a polynomial of degree d such that
P(x, f ) ≡ 0. Assuming P can be computed by a shallow circuit (or arithmetic formula) of size s, can f be
computed by a shallow circuit (or arithmetic formula) of size poly(s, n, d, r)?
In [8], the authors partially answer this question by showing that the polynomial f can be computed
by a shallow circuit of size poly(s, r, d degy (P) ). Thus, for the case of polynomials P which have small
individual degree with respect to y, they answer the question in the affirmative.
Our main technical observation, which we state next, gives an upper bound on the shallow circuit
complexity of polynomials f (x) ∈ F[x] of low degree such that there is a polynomial P(x, y) ∈ F[x, y]
with small shallow circuits satisfying P(x, f ) = 0. In other words, if we view P as a univariate polynomial
in y with coefficients coming from the ring F[x], then f is a low-degree polynomial that is a root of P. We
now state the theorem.
4 If we assume subexponential lower bound, then we can get a quasipolynomial time PIT. Note that this is the parameter
region used in [8].
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 5
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
Theorem 2.5. Let F be a field of characteristic zero. Let P ∈ F[x, y] be a polynomial of degree r in
n + 1 variables that can be computed by an arithmetic circuit of size s and depth ∆. Let f ∈ F[x] be a
polynomial of degree d such that
P(x, f ) = 0 .
√
Then, f can be computed by a circuit of depth ∆ + 3 and size O((srn)10 d O( d) ).
Furthermore, for any natural number k, f can be computed by a circuit of depth ∆ + O(k) and size
1/k
O((srn)10 d O(d ) ).
We conclude this section with a short discussion on the low-degree condition in the hypothesis
of Theorem 2.3.
2.2.1 The low-degree condition
The low-degree condition in the hypothesis of Theorem 2.3 appears to be extremely restrictive. It is natural
to wonder if the question of proving superpolynomial lower bounds for bounded-depth circuits for an
explicit family of polynomials of low degree is much harder than the question of proving superpolynomial
lower bounds for bounded-depth circuits for an explicit family of polynomials of potentially larger
degree? 5 Currently, we do not even know quadratic lower bounds for arithmetic circuits of bounded
depth, and so, perhaps we are quite far from understanding this question.
It is, however, easy to see that some of the known lower bounds for shallow circuits carry over to the
low-degree regime. For instance, the proofs of superpolynomial lower bounds for homogeneous depth-3
circuits by Nisan and Wigderson [28], superpolynomial lower bounds for homogeneous depth-4 circuits
based on the idea of shifted partial derivatives (see for example, [11, 19, 10, 23]) and superlinear lower
bound due to Raz [32] do not require the degree of the hard function to be large.
There are some known exceptions to this. For instance, lower bounds for√ homogeneous depth-5
circuits over finite fields due to Kumar and Saptharishi [22] are of the form 2Ω( d) and become trivial if
d < log2 n. Another result which distinguishes the low-degree and high-degree regimes is a separation
between homogeneous depth-5 and homogeneous depth-4 circuit [22] which is only known to be true in
the low-degree regime (degree less than log2 n).
Another result of relevance is a result of Raz [33], which shows that constructing an explicit family
of tensors Tn : [n]d → F, of rank at least nd(1−o(1)) implies superpolynomial lower bound for arithmetic
formulas, provided d ≤ O(log n/ log log n). As far as we know, we do not know of such connections in
the high-degree regime.
One prominent family of lower bound results which do not seem to generalize to this low-degree
regime are the superpolynomial lower bounds for multilinear formulas [31], and multilinear bounded-
depth circuits [35]. In fact, the results in [33] show that superpolynomial lower bounds for set multilinear
formulas6 for polynomials of degree O(log n/ log log n) imply superpolynomial lower bounds for general
arithmetic formulas.
5 In general, the degree only has to be bounded by a polynomial function in the number of variables.
6 Set multilinear formulas are a more structured sub-class of multilinear formulas and are a very natural model of computation
in certain settings. See [33] for a formal definition.
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 6
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
In the context of polynomial factorization, low-degree factors of polynomials with small circuits have
been considered before. For instance, Forbes [9] gave a quasipolynomial-time deterministic algorithm to
test if a given polynomial of bounded degree divides a given sparse polynomial. Extending this result
to even testing if a given sparse polynomial divides another given sparse polynomial remains an open
problem.
2.3 Factors of polynomials in VNP
We start by formally defining the complexity class VNP.
Definition 2.6 (VNP). A family of polynomials { fn } over a field F is said to be in the class VNPF if
there exist polynomially bounded functions k, w, v : N → N and a family {gn } in VPF such that for every
sufficiently large n ∈ N,
fn (x1 , x2 , . . . , xk(n) ) = ∑ gv(n) x1 , x2 , . . . , xk(n) , y1 , y2 , . . . , yw(n) .
y∈{0,1}w(n)
We refer to the y variables in the definition above as auxiliary variables, and the polynomial family gn
as the family of verifier polynomials. Essentially, VNP can be thought of as the algebraic analog of NP,
and understanding if VNP is different from VP is the algebraic analog of the famous P vs. NP question.
As discussed earlier in this section, Kaltofen’s closure result for VP does not seem to immediately
extend to VNP, and whether or not the factors of polynomials in VNP are in VNP was an open question.
Bürgisser made the following conjecture [4, Conjecture 2.1].
Conjecture 2.7 (Bürgisser). The class VNP is closed under taking factors.
As a direct application of our proof of Theorem 2.1, we confirm this conjecture over fields of
characteristic zero or of sufficiently large characteristic. We obtain a simple proof of the following
statement.
Theorem 2.8 (Informal). The class VNP is closed under taking factors.
The main technical statement which immediately gives us this closure result is the following theorem.
Theorem 2.9. Let F be a field of characteristic zero. Let P(x) be a polynomial of degree r over F, and
let Q(x, y) be a polynomial in n + m variables such that
P(x) = ∑ Q(x, y) ,
y∈{0,1}m
and Q can be computed by a circuit of size s. Let f be any irreducible factor of P of degree d. Then,
there exists an m0 ≤ poly(s, r, d, n, m) and polynomial h(x1 , x2 , . . . , xn , z1 , z2 , . . . , zm0 ) where h(x, z) can be
computed by a circuit of size s0 ≤ poly(s, r, d, n, m) such that
f (x) = ∑ h(x, z) .
0
z∈{0,1}m
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 7
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
We remark that in the proof of the above theorem, our techniques can be replaced by analogous
statements from [8, 29]. Although this is a simple observation, this does not appear to have been noticed
prior to this work. The best upper bound on the complexity of factors of polynomials in VNP in prior
work is a recent result of Dutta, Saxena, Sinhababu [7], who showed a bound of poly(n, r, s, m, d O(log d) )
on the number of auxiliary variables and the circuit complexity of verifier polynomials h.
As an easy consequence of our proofs, we also obtain another (slightly different) proof of the
following result of Dutta et al. [7].
Theorem 2.10 (Dutta, Saxena, Sinhababu). Let P(x) be a polynomial of degree r in n variables which
can be computed by an arithmetic formula (or algebraic branching program) of size s, and let f (x) be
a factor of P of degree d. Then, f (x) can be computed by an arithmetic formula (algebraic branching
program, resp.) of size poly(s, r, n, d O(log d) ).
3 Proof overview
The key technical ingredients of our results in this paper is Theorem 2.5. We start by describing the main
steps in its proof.
Proof sketch of Theorem 2.5. Our proof of Theorem 2.5 follows the outline of the proof of the
analogous theorem about the structure of roots in [8]. We now outline the main steps, and point out the
differences between the proofs. The first step in the proof is to show that one can use the standard Hensel
Lifting to iteratively obtain better approximations of the root f given a circuit for P(x, y). More formally,
in the kth step, we start with a polynomial hk which agrees with f on all monomials of degree k, and use it
to obtain a polynomial hk+1 which agrees with f on all monomials of degree k + 1. Moreover, the proof
shows that if hk has a small circuit, then hk+1 has a circuit which is only slightly larger than that of hk .
This iterative process starts with the constant term of f , which trivially has a small circuit. Thus, after
d iterations, we have a polynomial hd such that the root f is the sum of the homogeneous components
of hd of degree d. This lifting step is exactly the same as that in [8] or in some of the earlier works on
polynomial factorization [5], and is formally stated in Lemma 5.1.
The key insight of Dvir et al. [8] was that if degy (P) = t, and C0 (x),C1 (x), . . . ,Ct (x) are polynomials
such that P(x, y) = ∑ti=1 Ci (x)yt , then for every k ∈ {0, 1, . . . , d}, we have a polynomial Bk of degree k
such that
hk (x) = Bk (C0 (x),C1 (x), . . . ,Ct (x)) .
Now, consider the case when t n (for instance t = O(1)). It follows from standard interpolation
results for shallow circuits (see Lemma 4.9) that each of the polynomials Ci (x) has a circuit of size O(sr)
and depth ∆ since P has a polynomial of size s and depth ∆. Thus, hd (x) can be written as a sum of
d+t
t = O(d t ) monomials if we treat each Ci as a formal variable. Plugging in the small depth-∆ circuits
for each Ci , and standard interpolation (Lemma 4.9), it follows that f has a circuit of size poly(s, n, d t ) of
depth ∆ + O(1).
Observe that this size bound of poly(s, n, d t ) is small only when t is small. For instance, when
t > n, this bound becomes trivial. Our key observation is that independently of t, there is a set of d + 1
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 8
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
polynomials g0 (x), g1 (x), . . . , gd (x) of degree d, and polynomials A0 , A1 , . . . , Ak on d + 1 variables such
that for every k ∈ {0, 1, . . . , d},
hk (x) = Ak (g0 (x), g1 (x), . . . , gd (x)) .
Moreover, for every k, Ak has degree k and is computable by a circuit of size O(d 3 ). Also, each of
these generators gi can be computed by a circuit of size poly(s, r) and depth ∆. Thus, expressing
Ad (z0 , z1 , . . . , zd ) as a sum of monomials, and then composing this representation with the circuits for
g0 , g1 , . . . , gd would give us a circuit of size poly(s, n, r, d, 4d ) of depth ∆ + O(1). To get a subexponential
dependence on d in the size, we do not√write Ad (z0 , z1 , . . . , zd ) as ∑ ∏ circuit of size O(4d ), but instead
express it as a ∑ ∏ ∑ circuit of size d O( d) , using the depth-reduction result of [12].7
One point to note is that just from Kaltofen’s result [18], it follows that f has an arithmetic 8
√ circuit of
size poly(n). Thus, from Theorem 4.4, it follows that f has a circuit of depth-3 √
of size nO( d) . The key
O( d) ε
advantage of Theorem 2.5 over √ this bound is that the exponential term is d and not of the form nd .
For d ≤ log2 n/ log2 log n, d O( d) is bounded by a polynomial in n and so the final bound is poly(n).
Proof sketch of Theorem 2.1. To get Theorem 2.1 from Theorem 2.5, we also have to upper bound
the complexity of factors which are not of the form y − f (x), i. e., are non-linear in every variable. This
involves the use of some standard techniques in this area. We first preprocess P such that it is monic in y,
and then we work over the algebraic closure of the field F[x], and view P as a univariate in y over this
field. We then use Lemma 5.1 to approximate these roots by polynomials, and eventually combine them
using Lemma 6.3 from [29] to obtain the factor f . We get bounds on the circuit size and depth of the
factor f by keeping tab on the growth of these parameters in each step of the outlined algorithm.
Proof sketch of Theorem 2.3. Theorem 2.5, when combined with the standard machinery of Nisan-
Wigderson designs immediately yields Theorem 2.3.
Proof sketch of Theorem 2.9. For the proof of Theorem 2.9, we follow the same outline as above to
conclude that every factor f of a polynomial P = ∑y∈{0,1}m Q(x, y) can be written as
f (x) = H≤d [B(g0 (x), g1 (x), . . . , gd (x))] ,
where B has a circuit of size poly(d) and degree d and each polynomial gi can be expressed as
∑y∈{0,1}m0 Q̃i (x, y), where the number of auxiliary variables m0 and the circuit size of Q are each less than
poly(s, n, m, d, r), where s is the circuit size of Q, r is the degree of P. The proof follows from a result of
Valiant [40], where he showed that compositions such as B(g0 (x), g1 (x), . . . , gd (x)) can be written in the
form ∑y∈{0,1}m0 Q0 (x, y) with m00 and the circuit complexity of Q0 being poly(s, n, m, d, r).
7 See Theorem 4.4 for a formal statement of this result.
8 Of potentially very large depth.
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 9
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
Note that composing B and gi into the above form is not straightforward since direct replacement
of g0 with Q̃i might not work.9 For completeness, we include a proof of this using the depth-reduction
results in [41]. (See Theorem 8.2 and Claim 8.4 and the appendix for the proof.).
We remark that the proof outlined above bounds the complexity of the factor f once at the end of the
lifting, whereas in [7], the authors prove an upper bound on the number of auxiliary variables and the
circuit complexity of the verifier circuit for the approximation of the factor of P at the end of each step of
the lifting process. They show that in every step of lifting, these parameters grow only by a multiplicative
factor of d 2 , and there are O(log d) steps of lifting in total, hence the total blowup of d O(log d) in the
process. In contrast, we get a polynomial upper bound on the blowup in the number of auxiliary variables,
and the circuit size of the verifier circuit for the factor f , by a one step analysis.
Another crucial point to note is that Theorem 2.9 also follows if in the approach outlined above, we
replace our structure theorem for the structure of low-degree factors by an analogous statement in [8]
and [29]. This is because, the degree of the factor we are seeking and the depth of the circuit obtained for
the factor do not play a critical role in this proof as long as they are not too large. Thus, closure of VNP
under taking factors follows from the results known prior to this work, although as far as we know, this
does not seem to have been noticed before.
4 Preliminaries
We start by setting up some notation and stating some basic definitions and results from prior work which
will be used in our proofs.
4.1 Notation
• We use boldface letters x, y, z to denote a list of variables.
• For a function s : N → N, we say that s(n) ≤ poly(n), if there are constants n0 , a ∈ N such that
∀n > n0 , s(n) ≤ na .
• For a (multivariate) polynomial P, deg(P) denotes the total degree of P and degy (P) denotes the
degree of P with respect to the variable y.
• Let P ∈ F[x] be a polynomial. For every k ∈ N, Hk [P] denotes the homogeneous component of P
of degree k. Similarly, H≤k [P] is defined to be equal ∑ki=0 Hi [P].
• We say that a polynomial f is a factor of a polynomial P of multiplicity equal to m, if f m divides P,
and f m+1 does not divide P.
9 Consider the following toy example: Let B be a multiplication gate with two inputs from the same subcircuit g (x), i. e.,
0
B(g0 (x)) = g0 (x)2 . However, if we directly replace g0 (x) with Q̃0 , we would get ∑y∈{0,1}m0 Q̃i (x, y)2 , which might not be
g0 (x).
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 10
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
4.2 Arithmetic circuits
Definition 4.1 (Arithmetic circuits). An arithmetic circuit Ψ over a field F and variables x = (x1 , . . . , xn )
is a directed acyclic graph, the vertices of which we refer to as gates. The gates of in-degree zero (or
input gates) are labeled by elements in F and variables in x, and the internal gates are labeled by + (sum
gates) or × (product gates). The gates of out-degree zero in Ψ are called output gates. The circuit Ψ
computes a polynomial in F[x] in a natural way: the input gates compute the polynomial equal to its label.
A sum gate computes the polynomial equal to the sum of the polynomials computed at its inputs, while a
product gate computes the polynomial equal to the product of the polynomials computed at its inputs.
For an arithmetic circuit Ψ, we use size(Ψ) to denote the number of edges in Ψ. The depth of Ψ is
the length of the longest path from any input gate to any output gate. Throughout this paper, we assume
that all our circuits are layered with alternating layers of addition and multiplication gates, with the input
gates forming the bottom layer and the output gates forming the top layer. The directed edges should be
thought of as pointing upward. Moreover, we always assume that the top layer is of addition gates. For
instance, a depth-3 circuit is of the form ∑ ∏ ∑ and a depth-4 circuit is of the form ∑ ∏ ∑ ∏. Let P be the
polynomial computed by Ψ. For every k ∈ N, we use Hk [Ψ] to denote the homogeneous component of P
of degree k. Similarly, H≤k [Ψ] is defined to be equal ∑ki=0 Hi [Ψ].
4.3 Taylor’s expansion
A crucial tool for our proofs is the following classical lemma.
Lemma 4.2 (Taylor’s expansion). Let P(y) ∈ F[y] be a polynomial of degree d. Then,
P(2) (y) P(d) (y)
P(y + z) = P(y) + z · P(1) (y) + z2 · + · · · + zd · ,
2! d!
k
where, for every k, P() (y) = ∂ ∂P(y)
yk
is the derivative of order k of P with respect to y.
At a later point in the paper, we work with multivariate polynomials P(x, y) ∈ F[x, y] and view them
as univariate polynomials in y with the coefficients coming from the field of fractions F(x). In this case,
k
the derivatives P(k) (y) = ∂∂ yPk as defined above are elements of F[x].
4.4 Depth reduction
We will use the following depth-reduction theorems as a black boxes for our proofs. The first result is by
Agrawal–Vinay [1], Koiran [20], and Tavenas [39].
Theorem 4.3 (Depth reduction to depth (2k)). Let k be a positive integer and F be any field. If P(x) ∈ F[x]
is an n-variate polynomial of degree d that be computed by an arithmetic circuit Ψ of size s, then P can
1/k
be computed by a depth-(2k) circuit of size (snd)O(d ) .
√
Invoked with k = 2 the above theorem gives a circuit of depth 4 for the polynomial P of size sO( d) .
The next depth-reduction result, due to Gupta, Kamath, Kayal, and Saptharishi [12], gives a further
reduction to depth 3, as long as the field is of characteristic zero, and will be useful for our proof.
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 11
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
Theorem 4.4 (Depth reduction to depth 3). Let F be a field of characteristic zero. Let P(x) ∈ F[x] be an
n-variate polynomial of degree d that can be computed
√ by an arithmetic circuit Ψ of size s. Then, P can
be computed by a ∑ ∏ ∑ circuit of size (snd)O( d) .
We will also need the following two results which give formula upper bounds for polynomials with
small circuits. The results immediately follow from a classical depth-reduction result of Valiant, Skyum,
Berkowitz, and Rackoff [41].
Theorem 4.5 (Valiant et al.). Let P(x) be a polynomial of degree d in n variables which can be computed
by a circuit C of size s. Then, P can also be computed by a homogeneous circuit C0 of size poly(s, n, d),
with the following properties.
• Every product gate in C0 has fan-in at most 5.
• For every product gate g in C0 , the degree of the polynomial computed by any child of g is at most
half of the degree of the polynomial computed at g.
• C0 has alternating layers of sum and product gates, where the sum fan-ins can be unbounded.
Theorem 4.6 (Valiant et al.). Let P(x) be a polynomial of degree d in n variables which can be computed
by a circuit of size s. Then, P can also be computed by a formula of size (sn)O(log d) .
4.5 Explicit family of polynomials
The following definition is from Dvir, Shpilka, and Yehudayoff [8].
Definition 4.7 (Dvit et al.). Let { fm } be a family of multilinear polynomials such that fm ∈ Q[x1 , . . . , xm ]
for every m. Then, the family { fm } is said to be explicit if the following two conditions hold.
• All the coefficients of fm have bit complexity polynomial in m.
• There is an algorithm which on input m outputs the list of all 2m coefficients of fm in time 2O(m) .
4.6 Extracting homogeneous components
For our proofs, we will also rely on the following classical result of Strassen, which shows that if a
polynomial P has a small circuit, then all its low-degree homogeneous components also have small
circuits.
Theorem 4.8 (Homogenization). Let F be any field, and let Ψ ∈ F[x] be an arithmetic circuit of size s.
Then, for every k ∈ N, there is a homogeneous circuit Ψk of formal degree k and size O(k2 s), such that
Ψk = Hk [Ψ] .
Theorem 4.8 gives us a way of extracting homogeneous components of the polynomial computed by
a given circuit. We also need the following related well known lemma, whose proof we briefly sketch.
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 12
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
Lemma 4.9 (Interpolation). Let F be any field with at least d + 1 elements. Let P(x, y) ∈ F[x, y] be a
polynomial of degree d. Let C0 (x),C1 (x), . . . ,Cd (x) ∈ F[x] be polynomials such that P(x, y) = ∑dj=0 yd ·
C j (x). Then, if P(x, y) has a circuit of size s and depth ∆, then for every j ∈ {0, 1, . . . , d}, C j (x) has a
circuit of size O(sd) and depth ∆.
Proof sketch. For the proof, we view P as a univariate polynomial of degree d in y with coefficients in
the ring F[x]. Thus, each C j can be written as an appropriate linear combination of P(x, α0 ), P(x, α1 ), . . .,
P(x, αd ), where α0 , α1 , . . . , αd are distinct elements of the field F. Observe that for every α ∈ F, P(x, α)
has a circuit of size s and depth ∆. To compute C j , we have to take an appropriate linear combination of
these circuits, but the linear combination can be absorbed in the top sum gate, and hence this process
does not incur an increase in depth, while the size grows by a factor of at most d.
The following corollary of Lemma 4.9 would also be useful for us. The proof follows immediately
from the proof of Lemma 4.9.
Lemma 4.10 (Interpolation for formulas). Let F be any field with at least d + 1 elements. Let P(x, y) ∈
F[x, y] be a polynomial of degree d. Let C0 (x),C1 (x), . . . ,Cd (x) ∈ F[x] be polynomials such that P(x, y) =
∑dj=0 yd · C j (x). Then, if P(x, y) has a formula of size s, then for every j ∈ {0, 1, . . . , d}, C j (x) has a
formula of size O(sd).
4.7 Hitting sets
Definition 4.11. A set of points P is said to be a hitting set for a class C of circuits, if for every C ∈ C
which is not identically zero, there is an a ∈ P such that C(a) 6= 0.
Clearly, deterministic and efficient construction of a hitting set of small size for a class C of circuits
immediately implies a deterministic PIT algorithm for C. PIT algorithms designed in this way are also
black-box, in the sense that they do not have to look inside into the wiring of the circuit to decide if it
computes a polynomial which is identically zero. The PIT algorithms in this paper are all black-box in
this sense.
4.8 Nisan designs
We state the following well known result of Nisan [26] on the explicit construction of combinatorial
designs.
Theorem 4.12 (Nisan). Let n, m be positive integers such that n < 2m . Then, there is a family of subsets
S1 , S2 , . . . , Sn ⊆ [`] with the following properties.
• For each i ∈ [n], |Si | = m.
• For each i, j ∈ [n], such that i 6= j, Si ∩ S j ≤ log n.
m 2
• ` = O( log n ).
Moreover, such a family of sets can be constructed via a deterministic algorithm in time poly(n, 2` ).
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 13
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
4.9 The Polynomial Identity Lemma
We now state the well-known Polynomial Identity Lemma.10
Lemma 4.13 (Polynomial Identity Lemma). Let F be a field, and let P ∈ F[x] be a non-zero polynomial
of degree (at most) d in n variables. Then, for any finite set S ⊂ F we have
|{a ∈ Sn : P(a) = 0}| ≤ d|S|n−1 .
In particular, if |S| ≥ d + 1, then there exists some a ∈ Sn satisfying P(a) 6= 0. This gives us a brute
force deterministic algorithm, running in time (d + 1)n , to test if an arithmetic circuit computing a
polynomial of degree d in n variables is identically zero.
5 Low-degree roots of polynomials with shallow circuits
In this section, we prove Theorem 2.5, which is also our main technical observation. We start with the
following lemma, which gives us a way of approximating the root of a polynomial to higher and higher
accuracy, in an iterative manner. The lemma is a standard example of Hensel Lifting, which appears in
many of the prior works in this area including [8]. The statement and the proof below, are from Dvir et
al. [8].
Lemma
h i Lifting [8]). Let P ∈ F[x, y] and f ∈ F[x] be polynomials such that P(x, f ) = 0 and
5.1 (Hensel
H0 ∂ y (x, f (x)) = δ 6= 0. Let i ∈ {1, 2, . . . , deg( f )} be any number. If h ∈ F[x] is a polynomial such
∂P
that H≤i−1 [ f ] = H≤i−1 [h], then
P(x, h)
H≤i [ f ] = H≤i h − .
δ
Proof. For the rest of the proof, we think of P(x, y) as an element of F[x][y]. Henceforth, we drop the
variables x everywhere, and think of P as a univariate in y. Thus, P(y) = P(x, y). For brevity, we denote
H j [ f ] by f j for every j ∈ N.
From the hypothesis, we know that P( f ) = 0. Therefore, H≤i [P( f )] = H≤i−1 [P( f )] = 0. Moreover,
since H≤i−1 [h] = H≤i−1 [ f ], we get that H≤i−1 [P( f )] = H≤i−1 [P(h)] = 0. So, we have
0 = H≤i [P( f )]
= H≤i [P (h + ( fi − hi ))] .
We first observe that if fi = hi , then H≤i [P(h)] = 0, and the lemma is trivially true. So, for the rest of the
argument, we assume that fi − hi 6= 0. Now, by using Lemma 4.2, we get the following equality.
h i
0 = H≤i P(h) + P(1) (h) · ( fi − hi ) + P(2) (h) · ( fi − hi )2 /2! + · · · + P(r) (h) · ( fi − hi )r /r!
h i h i
= H≤i [P(h)] + H≤i P(1) (h) · ( fi − hi ) + · · · + H≤i P(r) (h) · ( fi − hi )r /r! .
10 Variants of this lemma, often referred to as the Schwartz–Zippel Lemma, or the DeMillo–Lipton–Schwartz–Zippel Lemma,
were discovered at least six times, starting with Øystein Ore in 1922 and David Muller in 1954 [30, 25, 36, 6, 42, 37]. For a
brief history, see [2] where the term “Polynomial Identity Lemma” is attributed to L. Babai.
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 14
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
Here, r denotes the degree of P. Since fi − hi is non-zero, and every monomial in fi − hi has degree equal
to i, any term in the above summand which is divisible by ( fi − hi )2 does not contribute any monomial of
degree at most i. Thus, we have the following.
h i
0 = H≤i [P(h)] + H≤i P(1) (h) · ( fi − hi )
h i
= H≤i [P(h)] + H0 P(1) (h) · ( fi − hi ) .
Now, we know that H0 [P0 (h))] = H0 [P0 ( f )] = δ 6= 0. Thus,
Hi [P(h)]
f i = hi − .
δ
Since H≤i−1 [P(h)] is identically zero, we get,
P(h)
H≤i [ f ] = H≤i h − .
δ
For our proof, we shall look at the structure of the outcome of the lifting operation in Lemma 5.1
more closely. Before proceeding further, we need the following crucial lemma.
Lemma 5.2. Let P(x, y) ∈ F[x, y] be a polynomial of degree r, let α ∈ F be a field element and d ∈ N be
a positive integer. Let G0y (P, α, d) be the set of polynomials defined as follows.
∂ jP
j
∂ P
G0y (P, α, d) = H≤d (x, α) − H0 (x, α) : j ∈ {0, 1, 2, . . . , d} .
∂yj ∂yj
Let Gy (P, α, d) be the subset of G0y (P, α, d) consisting of all non-zero polynomials. Then, the following
statements are true.
• For every g ∈ Gy (P, α, d), the degree of every non-zero monomial in g is at least 1 and at most d.
• |Gy | ≤ d + 1.
• If P has a circuit of size s and depth ∆, then every g ∈ Gy (P, α, d) has a circuit of size O(sr4 ) and
depth ∆.
Proof. The first two items follow immediately from the definition of Gy (P, α, d). We focus on the proof
of the third item. Let C0 (x),C1 (x), . . . ,Cr (x) be polynomials such that
r
P(x, y) = ∑ Ci (x) · yi .
i=0
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 15
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
j
Now, for any j ∈ {0, 1, 2, . . . , d}, by Lemma 4.2, ∂∂ yPj (x, y) is a scalar multiple of the coefficient of z j in
P(x, y + z). Moreover,
r
P(x, y + z) = ∑ Ci (x) · (y + z)i
i=0
!
r i
i j i− j
= ∑ Ci (x) · ∑ zy
i=0 j=0 j
!
r r
i
=∑ ∑ Ci (x) · yi− j · z j .
j=0 i= j j
Thus, for every j ∈ {0, 1, . . . , d}, the coefficient of z j in P(x, y + z) is given by ∑ri= j ij Ci (x) · yi− j .
From Lemma 4.9, we know that each Ci (x) has a circuit of depth ∆ and size at most O(sr). Thus, we
can obtain a circuit for ij Ci (x) · yi− j by adding an additional layer of × gates on top of the circuit
for Ci (x). This increases the size by an additive factor of r, and the depth by 1. However, observe
that this increase in depth is not necessary. Since, an expression of the form yi · (∑a ∏b Qa,b ) can be
simplified to ∑a yi · (∏b Qa,b ). Thus, the multiplication by yi can be absorbed in the product layer below
the topmost layer of the circuits for Ci (x), and this does not incur any additional increase in size. Thus,
j j
the polynomials ∂∂ yPj (x, y), and hence ∂∂ yPj (x, α) have a circuit of size O(sr3 ) and depth ∆. To compute the
homogeneous components of these polynomials of degree at most d, we use Lemma 4.9. This increases
the size by a factor of at most O(r2 ) while keeping the depth the same.
We now state our key technical observation.
Lemma 5.3. Let Ph∈ F[x, y] andi f ∈ F[x] be polynomials of degree r and d respectively such that
P(x, f ) = 0 and H0 ∂∂Py (x, f (x)) = δ 6= 0. Let the polynomials in the set Gy (P, H0 [ f ], d) be denoted by
g0 , g1 , . . . , gd . Then, for every i ∈ {1, 2, . . . , d}, there is a polynomial Ai (z) in d + 1 variables such that
the following are true.
• H≤i [ f ] = H≤i [Ai (g0 , g1 , . . . , gd )], and
• Ai (z) is computable by a circuit of size 10d 2 i.
This is an analog of the main technical lemma in [8], which we state below.
Lemma 5.4 ([8, Lemma 3.1]). Let h P ∈ F[x, y]i and f ∈ F[x] be polynomials of degree r and d respectively
such that P(x, f ) = 0 and H0 ∂∂Py (x, f (x)) = δ 6= 0. Let P(x, y) = ∑ki=0 Ci (x) · yi . Then, for every
i ∈ {1, 2, . . . , deg( f )}, there is a polynomial Ai (z) in k + 1 variables such that,
H≤i [ f ] = H≤i [Ai (C0 ,C1 , . . . ,Ck )] .
The difference between these lemmas is that in [8], it is shown that there is a set of polynomials of size
degy (P) + 1 which generate every homogeneous component of the root f . Thus, in the regime of bounded
individual degree, the size of this generating set is very small. However, when degy (P) ≥ n, Lemma 5.4
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 16
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
does not say anything non-trivial since f can be trivially written as a polynomial in the n original variables.
In contrast, Lemma 5.3 continues to say something non-trivial, as long as d n, regardless of the value
of degy (P). We now proceed with the proof.
Proof of Lemma 5.3. For the rest of the proof, we think of P(x, y) as an element of F[x][y]. So, we drop
the variables x everywhere, and think of P as a univariate in y. Thus, P(y) = P(x, y). For brevity, we
denote H j [ f ] by f j for every j ∈ N. We also use Gy for Gy (P, f0 , d). The proof will be by induction on i
and crucially use Lemma 5.1.
• Base case. We first prove the lemma for i = 1. We invoke Lemma 5.1 with i = 1 and h = f0 . We
get that
P( f0 )
H≤1 [ f ] = H≤1 f0 − .
δ
The proof follows by observing that f0 , δ are constants and H1 [P( f0 )] = H1 [g0 ] where g0 =
H≤d [P( f0 )] − H0 [P( f0 )] ∈ Gy .
• Induction step. We assume that the claim in the lemma holds up to homogeneous components
of degree at most i − 1, and argue that it holds for H≤i [ f ]. We invoke Lemma 5.1 with h =
Ai−1 (g0 , g1 , . . . , gd ), which exists by the induction hypothesis.
P(h)
H≤i [ f ] = H≤i h − .
δ
Recall that H0 (h) = H0 ( f ). Thus, h = f0 + h̃, where the constant term of h̃ is 0 and thus every
monomial has degree at least 1. By Lemma 4.2,
P( f0 + h̃) = P( f0 ) + P(1) ( f0 ) · h̃ + · · · + P(r) ( f0 ) · h̃r /r! .
Thus, as h̃ has degree at least 1, we have
1
H≤i [ f ] = H≤i h − · P( f0 ) + P ( f0 ) · h̃ + · · · + P ( f0 ) · h̃ /r!
(1) (r) r
δ
1
= H≤i h − · P( f0 ) + P(1) ( f0 ) · h̃ + · · · + P(i) ( f0 ) · h̃i /i! .
δ
Since we are only interested in i ≤ d, the following equality is also true.
1 h i h i
H≤i [ f ] = H≤i h − · H≤d [P( f0 )] + H≤d P ( f0 ) · h̃ + · · · + H≤d P ( f0 ) · h̃ /i! .
(1) (i) i
δ
Observe that for every j ∈ {0, 1, . . . , d}, H≤d P( j) ( f0 ) is an affine form in the elements of G.11 For
every j ∈ {0, 1, 2, . . . , i}, let ` j (z) be an affine form such that ` j (g0 , g1 , . . . , gd ) = H≤d P( j) ( f0 ) .
11 In fact, they are an affine form in one variable.
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 17
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
Now, we define Ai (z) as
1
`0 (z) + `1 (z) · (Ai−1 (z) − f0 ) + · · · + `i (z) · (Ai−1 (z) − f0 )i /i! .
Ai (z) ≡ Ai−1 (z) −
δ
The first item in the statement of the lemma is true, just by the definition of Ai (z) above. We now
argue about the circuit size of Ai (z). Each affine form `i (z) can be computed by a circuit of size
O(d). Thus, given a circuit of Ai−1 (z), we can obtain a circuit for Ai (z) by adding at most 10d 2
additional gates. Thus, Ai (z) can be computed by a circuit of size at most 10d 2 (i − 1) + 10d 2 =
10d 2 i gates.
The following is an easy corollary of Lemma 5.3.
Corollary 5.5. Let P(x, y) ∈ F[x, y] be a polynomial of degree, and α ∈ F be such that P(0, α) = 0, and
∂P
∂ y (0, α) 6= 0. Then, for every k ∈ N, there is a unique polynomial hk (x) such that deg(h) ≤ k, hk (0) = α,
and H≤k [P(x, hk (x))] = 0. Moreover, if the polynomials in the set Gy (P, α, k) be denoted by g0 , g1 , . . . , gk .
Then, there is a polynomial Ak (z) in k + 1 variables such that the following are true.
• hk = H≤k [Ak (g0 , g1 , . . . , gk )], and
• Ak (z) is computable by a circuit of size 10k3 .
The lemma initially starts with an α ∈ F such that α is a root of multiplicity 1 of P(0, y). And, starting
from this α, we can lift uniquely to a polynomial hi which is an approximate root of the polynomial P.
This corollary will be useful later on in the paper, when we study the structure of factors of P which are
not linear in y. And, the uniqueness will be important for this.
We are now ready to complete the proof of Theorem 2.5.
Proof of Theorem 2.5. The first step is to massage the circuit for P so that the hypothesis of Lemma 5.3
holds. We will have to keep track of the size and depth blowups incurred in the process. We begin by
ensuring that f is a root of multiplicity 1 of some polynomial related to P.
Reducing multiplicity of the root f . Let P(x, y) = ∑ri=0 yiCi (x). Let m ≥ 1 be the multiplicity of f as
j m
a root of P(x, y). Thus, ∂∂ yPj (x, f ) = 0 for j ∈ {0, 1, 2, . . . , m − 1}, but ∂∂ ymP (x, f ) 6= 0. The idea is to just
m−1
work with the polynomial P̃ = ∂∂ ym−1P (x, y) for the rest of the proof. Clearly, f is a root of multiplicity
exactly 1 of P̃. We only need to ensure that P̃ can also be computed by a small shallow circuit. This
j
follows from the proof of the third item in Lemma 5.2, where we argued that ∂∂ yPj (x, y) has a depth-∆
circuit of size poly(s, r).
Translating the origin. From the step above, we can assume without loss of generality that ∂∂Py (x, f ) 6=
0. Thus, there is a point a ∈ Fn such that ∂∂Py (a, f (a)) 6= 0. By translating the origin, we will assume that
∂P
∂ y (0, f (0)) 6= 0. This increases the depth of the circuit by at most 1, as it could involve replacing every
variable xi by xi + ai , and the size by a factor of at most n.
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 18
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
Degree of Ad . From Lemma 5.3, we know that the polynomial Ad (z) has a circuit of size O(d 3 ). To
obtain a circuit for f , we first prune away all the homogeneous components of Ad (z) of degree larger
than d. Recall that by definition, for every polynomial gi ∈ Gy , every non-zero monomial in gi has degree
at least 1, and that f = H≤d [Ad (g1 , g2 , . . . , gd )]. Thus, any monomial of degree strictly greater than d
in Ad (z) contributes no monomial of degree at most d in the variables x in the composed polynomial
Ad (g1 , g2 , . . . , gd ), and hence does not contribute anything to the computation of f . So, we can confine
ourselves to working with the homogeneous components of Ad (z) of degree at most d.
By Theorem 4.8, we know that given a circuit for Ad (z), we can construct a circuit for Hi [Ad (z)] by
increasing the size of the circuit by a multiplicative factor of at most O(i2 ). Thus, H≤d [Ad (z)] can be
computed by a circuit of size O(d 3 ) × size(Ad (z)). Thus, for the rest of this argument, we will assume
that Ad (z) has a circuit of size O(d 6 ) and degree at most d, and
f = H≤d [Ad (g1 , g2 , . . . , gd )] .
Shallow Circuit for Ad (z). Given that Ad (z) has a circuit of size O(d 6 ) and degree at most
√
d, by Theo-
rem 4.4, we know that Ad (z) can be computed by a ∑ ∏ ∑ circuit Ψ of size at most d O( d) . Similarly,
by Theorem 4.3, we know that for any k ∈ N, Ad (z) can be computed by a depth-(2k) circuit of size
1/k
d O(d ) .
Shallow circuit for f . Composing the ∑ ∏ ∑ circuit Ψ for Ad (z) with the circuits of g1 , . . . , gd ∈ Gy ,
we get a circuit Ψ0 with the following properties.
√
• The size of Ψ0 is (srn)10 · d O( d) ).
• The depth of Ψ0 is at most ∆ + 3. This follows by combining the bottom ∑ layer of the ∑ ∏ ∑
circuit for Ad (z) with the top ∑ layer of the circuits for gi ∈ Gy .
• The degree of Ψ0 is at most d 2 . This is true because the degree of Ad (z) is at most d (as argued earlier
in this proof), and the degree of every polynomial in Gy is at most d (first item in Theorem 5.2).
• f = H≤d [Ψ0 (x)].
1/k
Note that for any k ∈ N, we can get Ψ0 of size (srn)10 · d O(d ) ) and of depth at most ∆ + O(k).
To obtain a circuit for f , we apply Lemma 4.9 to Ψ0 . This increases the size of Ψ0 by a multiplicative
factor of at most O(d 2 ), while the depth remains the same. This completes the proof of the theorem.
6 From roots to arbitrary factors
In this section, we show that Theorem 2.5 essentially generalizes to arbitrary factors, and not necessarily
factors of the form y − f (x), up to some loss in the size and depth parameters. The techniques for this
generalization are quite standard and well known in this literature, and our presentation here follows the
approach of Oliveira [29]. We sketch the main steps towards obtaining circuits for arbitrary factors.
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 19
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
Making the polynomial monic in y. Starting with an arbitrary polynomial P(x, y), we first make sure
that it is monic in y. We do this by taking an invertible linear transformation xi → xi + ai · y, where the
vector a is chosen randomly from some large enough grid. Indeed, assume that deg(P) = r. Let us
consider the homogeneous component of degree r of P(x, y). Since Hr [P(x, y)] is homogeneous in (x, y)
of degree r, so Hr [P(x, y)] = Pr (x/y, 1) · yr for a polynomial Pr , implying that Pr (x/y, 1) is not the zero
polynomial, so we can write
P(x + ay, y) = Pr (a, 1)yr + lower order terms (in y) .
By Lemma 4.13, there exists some a ∈ [r + 1]n , with Pr (a, 1) 6= 0. Thus, in the inverted coordinate
system, the leading coefficient of P(x + ay, y) (as a polynomial in y), is some non-zero element of the
field F, and, without loss of generality, we can take it to be 1.
If P(x, y) is monic, then so are its factors. To see this, first recall the Gauss Lemma. We shall use it to
deduce that the factors of P(x, y) are elements in F[x, y].
Lemma 6.1 (Gauss Lemma). Let R be a Unique Factorization Domain with a field of fractions F and let
f (y) ∈ R[y]. If f (y) is reducible over F[y], then f is reducible over R[y].
Now, we have the following simple observation.
Observation 1. Let R = F[x]. If P ∈ R[y] is a monic polynomial in y, and P = g · h, where g, h ∈ R[y],
then the leading coefficients of g and h in y belong to F \ {0}.
Thus, for the rest of this section, we will assume that all the factors of P(x, y) are also monic in y.
Working over the algebraic closure of F(x). As above, P is monic in y with degy (P) = r, that is,
r−1
P(x, y) = yr + ∑ Pr (x)yi .
i=0
Assume that P does not factor into linear factors in y, and that f (x, y) is one of its factors, of degree k in y.
Since P is monic in y, we know that f must also be monic in y. Working over the algebraic closure of
F(x) (that is, the field F(x)), we can factor P (and f ) into linear factors in y. The algebraic closure of
F(x) is a complicated object, but we only need to think of elements of the closure as “functions” over the
variables in x. Since f divides P , if
r
P(x, y) = ∏(y − ϕi (x)) ,
i=1
without loss of generality, assume the first d of these ϕi correspond to roots of f , so we have
d
f (x, y) = ∏(y − ϕi (x)) .
i=1
We note that ϕi (x) may not be polynomials in x.12 Still, the fact that they share some roots in the closure
of F(x) gives us a way to approximate them, using Hensel’s lifting, similar to Lemma 5.3. For the rest of
our argument, we first need to ensure some non-degeneracy conditions.
12 As shown in [7], ϕ (x) could be a power series in x.
i
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 20
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
Reducing the multiplicity of f in P. We first make sure that f is a factor of multiplicity 1 of P; if f is
m−1
a factor of multiplicity m > 1, we can replace P by P̃ = ∂∂ ym−1P (x, y). Clearly, f is a factor of multiplicity
exactly 1 of P̃. Ensuring that P̃ can also be computed by a small shallow circuit, follows from the proof
j
of the third item in Lemma 5.2, where we argued that ∂∂ yPj (x, y) has a depth-∆ circuit of size O(sr3 ). So,
for the rest of the proof, we will assume that f is a factor of P of multiplicity equal to 1.
Properly separating shifts. To proceed further, we want a shift in x such that each factor has no
repeating roots in y and distinct factors share no root in y. This follows from the below lemma from [29],
which we state without a proof.
Lemma 6.2 ([29, Lemma 3.6]). Let f (x, y), g(x, y) ∈ F[x, y] be polynomials such that degy ( f ) ≥ 1,
n
degy (g) ≥ 1, f is irreducible and f does not divide g. Then, there is a c ∈ F such that
• f (c, y) is a polynomial with exactly degy ( f ) distinct roots in F, and
• f (c, y) and g(c, y) have no common roots.
Now, let us consider the polynomial g = P/ f . Since f is factor of multiplicity 1 of P, f does not
divide g. From Lemma 6.2, we know that there is a c ∈ Fn such that f (c, y) and g(c, y) do not share a
root, and all the roots of f (c, y) are distinct. At the cost of increasing the depth of the circuit of P by 1,
we can assume without loss of generality that c is the origin. So, for the rest of the proof, we assume that
f (0, y) has no repeating roots, and f (0, y) and g(0, y) share no common roots. Let α1 , α2 , . . . , αr be the
roots of P(0, y) and let α1 , α2 , . . . , αd be the roots of f (0, y).
Approximating the roots of P. The goal of this step is to approximate the roots of P by low-degree
polynomials with small circuits. From the previous paragraph, we know that for i ∈ [d], P(0, αi ) = 0 and
∂P
∂ y (0, αi ) 6= 0. Thus, from Corollary 5.5, there are polynomials q1 , q2 , . . . , qd of degree at most d such
that for every i ∈ [d], there is a polynomial Ai,d (z) in d + 1 variables such that the following are true.
• qi (0) = α, and
• qi = H≤d [Ai,d (gi,0 , gi,1 , . . . , gi,d )], and
• Ai,d (z) is computable by a circuit of size at most 10d 3 .
Here, for every i ∈ [d], gi,0 , gi,1 , . . . , gi,d are the polynomials in the set Gy (P, αi , d). Thus, we have degree
d polynomials, which are approximations of the roots of P, the constant terms of these polynomials agree
with the roots of f (x, 0) and these approximate roots have small shallow circuits. Moreover, We will now
combine these approximations to obtain a circuit for f .
Obtaining a circuit for f . In this final step, we are going to obtain circuit for f from the polynomials
q1 , q2 , . . . , qd in the previous step. The first observation is that the q1 , q2 , . . . , qd are also approximate
roots of the polynomial f . To see this, observe that by our choice, α1 , α2 , . . . , αd are distinct roots of
f (0, y). Thus, for each i ∈ [d], f (0, αi ) = 0 and ∂∂ yf (0, αi ) 6= 0. Thus, by Corollary 5.5, there are degree
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 21
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
d polynomials q̃1 , q̃2 , . . . , q̃d of degree at most d such that H≤d [ f (x, q̃i (x))] = 0. Thus, we also have
H≤d [P(x, q̃i (x))] = 0. So, by the uniqueness condition in Corollary 5.5, we get that the set of polynomials
{q̃i : i ∈ [d]} must be the same as {qi : i ∈ [d]}.
Next, to obtain a circuit for f , we now claim that
" #
d
f (x, y) = H≤d ∏ (y − qi (x)) .
i=1
The proof of this fact follows immediately from Lemma 5.4 in [29]. We state a special case, which
suffices for our application.
Lemma 6.3 ([29, Lemma 5.4]). Let P(x, y) and f (x, y) be polynomials of degree r and d respectively,
such that P and f are monic in y, f is a factor of P and all the roots of f (0, y) are distinct and roots of
multiplicity exactly one of P(0, y). Let α1 , α2 , . . . , αd be the roots of f (0, y) and let q1 , q2 , . . . , qd ∈ F[x]
be polynomials of degree at most d such that for every i ∈ [d],
• qi (0) = αi ,
• H≤d [P(x, qi (x))] = H≤d [ f (x, qi (x))] = 0.
Then, " #
d
f = H≤d ∏ (y − qi (x)) .
i=1
Thus, given the circuits for qi (x), we can obtain a circuit for f (x, y) by increasing the depth by at most
two (a product layer, and then a sum layer for interpolation), and size by a poly(d) factor. In summary,
we have the following two statements.
Lemma 6.4. Let P ∈ F[x, y] and f ∈ F[x, y] be polynomials of degree r and d respectively such that
P is monic in y and f is an irreducible factor of P. Then, there exist c ∈ Fn , α1 , α2 , . . . , αd ∈ F and a
polynomial B(z) of degree at most d in t = O(d 2 ) variables, such that the following are true.
• f (x + c, y) = H≤d [B (g0 , g1 , . . . , gt )], where g1 , g2 , . . . , gt are polynomials in the set
d
Gy (P(x + c, y), αi , d) .
[
i=1
• B(z) is computable by a circuit of size poly(d).
Theorem 6.5. Let P ∈ F[x, y] be a polynomial of degree r in n + 1 variables that can be computed by an
arithmetic circuit of size s of depth ∆. Let f ∈ F[x, y] be an irreducible polynomial of degree d √such that
f divides P. Then, f can be computed by a circuit of depth ∆ + O(1) and size poly(s, r, n) · d O( d) .
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 22
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
7 Deterministic PIT for shallow circuits from hardness
In this section, we use Theorem 2.5 to show that given a family of polynomials which are hard for depth
∆ circuits, we can do deterministic identity testing for ∆ − 5 circuits in subexponential time. In short, the
high-level strategy is to generate hitting set for shallow circuits from the hard polynomial combined with
Nisan designs. Since the content of this part is very similar to the proofs of similar statements in [13]
and [8], we only outline the differences in the proofs (if any), and refer the reader to [8] for details. We
start with the following lemma, which is the analog of Lemma 4.1 in [8].
Lemma 7.1 (Analog of Lemma 4.1 in [8]). Let q(x) ∈ F[x] be a (non-zero) polynomial of degree D in
n variables, which can be computed by a circuit of size s and depth ∆. Let m > log n be an integer and
let S1 , S2 , . . . , Sn ⊆ [`] be given by Theorem 4.12, so that ` = O(m2 / log n), |Si | = m, and Si ∩ S j ≤ log n.
For a multilinear polynomial f ∈ F[z1 , z2 , . . . , zm ] of degree d, put
Q(y) = Q(y1 , y2 , . . . , y` ) := q ( f (y|S1 ), f (y|S2 ), . . . , f (y|Sn )) .
√
If Q(y) ≡ 0, then f (z) can be computed by an arithmetic circuit of size O((snD)12 d O( d) ) and depth at
most ∆ + 5.
Note that the bound on the size of f remains non-trivial as long as d m, while the individual degree
of q is allowed to be unbounded, whereas the bound in [8] becomes trivial once degy (q) is larger than m.
Proof Sketch. The proof is along the lines of the proof of Lemma 4.1 in [8]. We now give a sketch of the
details. We first define the hybrid polynomials Q0 (x, y), Q1 (x, y), . . . , Qn (x, y) as follows.
Q j (x, y) = q f (y|S1 ), f (y|S2 ), . . . , f (y|S j ), x j+1 , x j+2 , . . . , xn .
We know that Q0 (x, y) is non-zero, whereas Qn (x, y) is identically zero. Thus, there is an i ∈ {0, 1, . . . , n}
Qi (x, y) 6≡ 0 and Qi+1 (x, y) ≡ 0. We now fix the variables xi+2 , xi+3 , . . . , xn and the vari-
such that
ables y j : j ∈ / Si+1 to field constants while maintaining the non-zeroness of Qi . This can be done
via Lemma 4.13. Thus, we have a polynomial q̃ by fixing the aforementioned variables such that the
following two conditions hold.
q̃ f (y|S1 ∩Si+1 ), f (y|S2 ∩Si+1 ), . . . , f (y|Si ∩Si+1 ), xi+1 6≡ 0 .
q̃ f (y|S1 ∩Si+1 ), f (y|S2 ∩Si+1 ), . . . , f (y|Si ∩Si+1 ), f (y|Si+1 ) ≡ 0 .
Let A0 (y|Si+1 , xi+1 ) denote the polynomial q̃ f (y|S1 ∩Si+1 ), f (y|S2 ∩Si+1 ), . . . , f (y|Si ∩Si+1 ), xi+1 . The above
two conditions imply that f (y|Si+1 ) is a root of the polynomial A0 (y|Si+1 , xi+1 ) ∈ F[y|Si+1 ][xi+1 ], viewed
as a polynomial in xi+1 . Moreover, A0 (y|Si+1 , xi+1 ) has a circuit of size O(sn) and depth at most ∆ + 2.
This follows from the fact that f (y|S1 ∩Si+1 ) is a multilinear polynomial in log n variables, and can thus be
computed by a ∑ ∏ circuit of size at most n. We simply replace the variables x1 , x2 , . . . , xi in the circuit for
q by these ∑ ∏ circuits to obtain a circuit for A0 . The degree of A0 is at most D √log n. Finally, Theorem
√ 2.5
implies that f (y|Si+1 ) can be computed by a circuit of size O(poly(s, n, D)d O( d) ) poly(s, n, D)d O( d) and
depth at most ∆ + 5, thus completing the proof.
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 23
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
We now sketch the proof of Theorem 2.3.
Proof Sketch. Once again, the proof follows the proof of Theorems 1 and 2 in [8]. Let { fm } be an explicit
family of multilinear polynomials such that fm has m variables, degree
2 !
log m
d≤O ,
log log m
such that fm cannot be computed by a circuit of depth ∆ and size poly(m). Let ε ∈ (0, 0.49) be an arbitrary
constant, and set m := nε , and f = fm .
Given as input a circuit C ∈ F[x] of size s, depth ∆ − 5 and degree D on n variables, let q ∈ F[x] be the
polynomial computed by C. The goal here is to determine whether q is non-zero. From the equivalence
of black-box PIT and hitting set, it suffices to construct hitting sets for the circuit class with the above
properties.
• We construct a design S1 , S2 , . . . , Sn ⊆ [`] using Theorem 4.12 where each set Si has size m,
2ε
` = O(m2 / log n) ≤ n2ε < n0.98 and Si ∩ S j ≤ log n. This can be done in deterministic time 2O(n ) .
• We pick a subset T of the field F of size Dd + 1 and evaluate the polynomial
q ( f (y|S1 ), f (y|S2 ), . . . , f (y|Sn ))
on all points of T ` .
H = {( f (y|S1 ), f (y|S2 ), . . . , f (y|Sn )) | y ∈ T ` }
2ε 0.98 )
is then our candidate hitting set of size (Dd + 1)` = nO(n ) < nO(n . Note that the set can be
2ε 2ε
constructed deterministically in time md · nO(n ) = nO(n ) .
We now argue about the correctness, i. e., q does not vanish on the hitting set if and only if q is not
identically zero. Observe that if the polynomial q ( f (y|S1 ), f (y|S2 ), . . . , f (y|Sn )) is not identically zero,
then it has degree at most Dd and hence by Lemma 4.13, q does not vanish on the set H. Else,
q ( f (y|S1 ), f (y|S2 ), . . . , f (y|Sn )) ≡ 0.√But then, by Lemma 7.1, we get that f can be computed by a circuit
of depth ∆ and size poly(s, n, D)d O( d) . If s, D are poly(n), then this bound is poly(m) which contradicts
the assumed hardness of f = fm for circuits of depth ∆. This shows that H is a hitting set for the desired
circuit class and completes the proof.
8 Factors of polynomials in VNP
We now prove Theorem 2.9, which is restated below.
Theorem 8.1 (Theorem 2.9 restated). Let P(x) be a polynomial of degree r over F, and let Q(x, y) be a
polynomial in n + m variables such that
P(x) = ∑ Q(x, y) ,
y∈{0,1}m
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 24
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
and Q can be computed by a circuit of size s. Let f be an irreducible factor of P of degree d. Then, there
exists an m0 ≤ poly(s, r, d, n, m) and polynomial h(x, z1 , z2 , . . . , zm0 ), such that h(x, z) can be computed by
a circuit of size s0 ≤ poly(s, r, d, n, m) and
f (x) = ∑ h(x, z) .
0
z∈{0,1}m
For our proof, we use the following structure theorem of Valiant [40], and its consequences (Claim 8.4).
Below, we state the theorem, and then use it to prove Theorem 8.1. For completeness, we include a proof
using the depth-reduction results in [41] in the appendix.
Theorem 8.2 (Valiant [40]). Let P(x) be a homogeneous polynomial of degree r in n variables that can
be computed by an arithmetic circuit C of size s. Then, there is an m ≤ poly(s, r) and a polynomial
Q(x, y1 , y2 , . . . , ym ) such that
P(x) = ∑ Q(x, y) ,
y∈{0,1}m
and Q(x, y) can be computed by an arithmetic formula of size poly(s, r).
We now proceed with the proof of Theorem 8.1.
Proof of Theorem 8.1. Without loss of generality, we will assume that P is monic in a variable z. This
can be guaranteed by doing a linear transformation by replacing every variable xi by xi + ai z, where ai are
chosen from a large enough grid, based on the degree of P. Note that this preserves the form of P in the
hypothesis of the theorem. Moreover, using Theorem 4.8, we will assume that the degree of Q(x, y) in
the variables x and z is r, up to a polynomial blowup in the circuit size of Q.
From Lemma 6.4, we know that there is a c ∈ Fn and a polynomial B in at most t = O(d 2 ) variables,
and polynomials g1 , g2 , . . . , gt such that
f (x + c, z) = H≤d [B(g1 , g2 , . . . , gt )] .
For the rest of this proof, we assume that we have shifted the origin, so that c = 0. Again, this just requires
replacing every variable xi by xi + ci , and this shift of coordinates does not affect the structure of P in the
hypothesis of the theorem. Thus,
f (x, z) = H≤d [B(g1 , g2 , . . . , gt )] .
Moreover, B has a circuit of size poly(d) and each gi belongs to some set Gz (P, α, d) for some α ∈ F.
We now need the following two structural claims which follow from direct applications of properties of
polynomials in VNP as shown by Valiant [40].
Claim 8.3 (Valiant [40]). For every choice of α ∈ F and g j ∈ Gz (P, α, k), there is a polynomial
Q0j (x, y1 , y2 , . . . , ym )
such that
g j (x) = ∑ Q0j (x, y) .
y∈{0,1}m
Moreover, Q0 can be computed by a circuit of size poly(s, r, d).
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 25
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
The second claim is about the structure of the composed polynomial B(g1 , g2 , . . . , gt ). This is a special
case of a more general result of Valiant [40], which showed that VNP is closed under composition.
Claim 8.4 (Valiant [40]). There is an m̃ ≤ poly(m, d) and a polynomial Q̃(x, y1 , y2 , . . . , ym̃ ) such that
B(g1 , g2 , . . . , gt ) = ∑ Q̃(x, y) .
y∈{0,1}m̃
Moreover, Q̃ can be computed by a circuit of size poly(s, r, d, n, m).
For completeness, we provide a sketch of the proofs of the claims and that of Theorem 8.2 to the
appendix. We now use the claims above to complete the proof of Theorem 8.1.
Observe that if we view Q̃ as a polynomial in x variables with coefficients coming from F[y], then,
for every k ∈ N, it follows that
Hk [B(g1 , g2 , . . . , gt )] = ∑ Hk,x Q̃(x, y) .
y∈{0,1}m̃
Here, Hk,x [Q̃(x, y)] denotes the homogeneous component of degree k of Q̃(x, y) when viewing Q̃(x, y) as
a polynomial in x variables. It follows from Theorem 4.8, that by blowing up the size of the circuit for Q̃
by a factor of O(k2 ), we can obtain a circuit which computes Hk,x [Q̃(x, y)], and this does not affect the y
variables in any way. This gives us a representation of f (x, z) as
f (x) = ∑ h(x, z)
0
z∈{0,1}m
where m0 = m̃ ≤ poly(m, d), and h can be computed by a circuit of size poly(s, r, d, n, m). This completes
the proof of the theorem.
9 Factors of polynomials with small formulas
In this section, we prove the following theorem, which gives an upper bound on the formula complexity
of factors of polynomials which have small formulas. We note that this result is not new and was also
proved by Dutta et al. in [7]. Since the proof essentially follows from our techniques developed so far and
our proof is different from the proof in [7], we include the statement and a proof sketch.
Theorem 9.1 ([7]). Let P(x) be a polynomial of degree r in n variables which can be computed by an
arithmetic formula of size s, and let f (x) be a factor of P of degree d. Then, f (x) can be computed by an
arithmetic formula of size poly(s, r, n, d O(log d) ).
Proof. The proof is again along the lines of the proof of Theorem 8.1. We first observe that the
polynomials in Gy (P, α, k) have small formulas. This just follows from the proof of Item 3 in Lemma 5.2
and Lemma 4.10.
Now, recall that from Lemma 6.4, we know that the B is a polynomial in at most O(d 2 ) variables, and
can be computed by a circuit of size poly(d). Thus, by Theorem 4.6, we get that B can be computed by a
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 26
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
formula Φ of size at most d O(log d) . Composing Φ with the formulas for the polynomials in Gy (P, α, k),
we get a formula for B(g1 , g2 , . . . , gt ) of size poly(r, s, m, n, d O(log d) ), and also,
f = H≤d [B(g1 , g2 , . . . , gt )] .
All we need now to complete the proof, is a formula for H≤d [B(g1 , g2 , . . . , gt )], and this follows
from Lemma 4.10.
We remark that the proof extends to the model of algebraic branching programs. More precisely, the
following statement is true.
Theorem 9.2. Let P(x) be a polynomial of degree r in n variables which can be computed by an algebraic
branching program of size s, and let f (x) be a factor of P of degree d. Then, f (x) can be computed by an
algebraic branching program of size poly(s, r, n, d O(log d) ).
10 Proofs of claims
We now include the proofs of Theorem 8.2, Claim 8.3 and Claim 8.4. We follow the notation set up in the
proof of Theorem 8.1.
Proof of Claim 8.3. We relabel one of the variables in x as z. Let C0 (x),C1 (x), . . . ,Cr (x) be polynomials
such that
r
P(x, z) = ∑ Ci (x) · zi .
i=0
j
Recall that ∂∂ zPj (x, z) equals j! · ∑ri= j ij Ci (x) · zi− j . Now, we know that
P(x, z) = ∑ Q(x, y, z) .
y∈{0,1}m
Expressing Q(x, y, z) as a univariate in z, we get
r
Q(x, y, z) = ∑ Ci0 (x, y) · zi .
i=1
Recall that Q(x, y, z) has a circuit of size poly(s) and degree at most r. By viewing Q as a univariate in
z and applying Theorem 4.8, we get that each Ci0 (x, y) has a circuit of size poly(s, r). In particular, for
every j ∈ N, we can write C j (x) as
C j (x) = ∑ C0j (x, y) .
y∈{0,1}m
Therefore, for every j ∈ {0, 1, 2, . . . , d}, we get
!
r r
i i− j i 0 i− j
∑ Ci (x) · z = ∑ m ∑ j Ci (x, y) · z .
i= j j y∈{0,1} i= j
Moreover, the polynomial ∑ri= j ij Ci0 (x, y) · zi− j has a circuit of size poly(n, r). This completes the
proof of the claim.
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 27
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
Proof of Claim 8.4. The proof is in two parts. We first define the construction of the circuit for Q̃, and
then argue the correctness of this construction.
Constructing Q̃. We know that B(z1 , z2 , . . . , zt ) is of degree at most d and can be computed by a circuit
of size poly(d). It follows from Theorem 8.2, that there is an a ≤ poly(t, d) and a polynomial B0 in at
most t + a variables such that
B(z1 , z2 , . . . , zt ) = ∑ B0 (z, y) .
y∈{0,1}a
Crucially, it is also the case that B0 has a formula of size poly(d,t). We remark that it is extremely
important for the proof that B0 has a small formula, and not just a small circuit. To construct Q̃, we
consider the formula Φ for B0 (z, y) and let `1 , `2 , . . . , `u be the input gates of Φ. Each of these input
gates is labeled by a z variable, a y variable or a field constant. From this, we construct a circuit
Φ0 by going through over the input gates, and replacing the gate `i by the circuit for polynomial
Q0j (x, yi ) from Claim 8.3 if it is labeled by z j and leaving it unchanged otherwise. Thus, Φ0 computes
polynomial in variables x ∪ y ∪ ( uj=1 y j ), of size poly(s, d, r, n, m). We denote this polynomial by Q̃. Let
S
Su
m̃ = |x ∪ y ∪ ( j=1 y j )| ≤ poly(m, d). We now argue that the construction in correct.
Correctness. We now argue that
B(g1 , g2 , . . . , gt ) = ∑ Φ0 (x, y, y1 , . . . , yu ) .
(y,y1 ,...,yu )∈{0,1}m̃
The proof is by an induction on the size of formula Φ and the fact that in going from Φ to Φ0 , each of the
input gates of Φ which was labeled by a z j variable was replaced by a copy of Q0j with a unique copy of
the auxiliary y variables. Note that the uniqueness of the auxiliary variables is due to the fact that B0 has a
formula. Finally, the proof follows from the following observation showing that m̃ = poly(s,t, d). We
skip the details.
Observation 1. Let R1 (x), R2 (x) and S1 (x, y), S2 (x, z) be polynomials such that
R1 (x) = ∑ S1 (x, y) , and
y∈{0,1}|y|
R2 (x) = ∑ S2 (x, z) .
z∈{0,1}|z|
Then,
R1 (x) + R2 (x) = ∑ (S1 (x, y) + S2 (x, z)) , and
y∈{0,1}|y| ,z∈{0,1}|z|
R1 (x) × R2 (x) = ∑ (S1 (x, y) × S2 (x, z)) .
y∈{0,1}|y| ,z∈{0,1}|z|
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 28
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
Proof of Theorem 8.2. Let C0 be the circuit obtained by applying Theorem 4.5 to the circuit C. The idea
is to inductively turn C0 into a formula while reducing the depth by half in every step. From the properties
of C0 , we get that
s0
P = ∑ Ai,1 · Ai,2 · · · Ai,5 .
i=1
Here s0 ≤ poly(s, n, d) is the size of C0 , and every Ai, j is a polynomial computed by a subcircuit in C0
and the degree of Ai, j is at most d/2 + 1. We introduce variables yi, j , i ∈ [s0 ], j ∈ [5] . Let R(y) be the
following polynomial.
s 0
R(y) = ∑ (yi,1 · yi,2 · · · yi,5 ) · ∏ (1 − yi0 ,1 )(1 − yi0 ,2 ) · · · (1 − yi0 ,5 )
i=1 i0 6=i
Observe that for b ∈ {0, 1}|y| , R(b) is 1 if and only if there is an i ∈ [s0 ] such that (bi,1 , bi,2 , bi,3 , bi,4 , bi,5 )
equals (1, 1, 1, 1, 1) and for all i0 ∈ [s0 ] with i 6= i0 , (bi0 ,1 , bi0 ,2 , bi0 ,3 , bi0 ,4 , bi0 ,5 ) = (0, 0, 0, 0, 0), and zero
otherwise. Moreover, R(y) can be computed by an arithmetic formula of size s02 = poly(s). Now, observe
that we can write the polynomial P as follows.
!
5 s0
P(x) = ∑ R(y) · ∏ ∑ Ai, j yi, j .
0 j=1 i=1
y∈{0,1}5s
0
Also, for every j, the polynomial ∑si=1 Ai, j yi, j is of degree at most d/2 + 1 and can be computed by a
circuit of size at most 3s0 . This is true since each Ai, j is computed by a subcircuit of C0 . Thus, we have
expressed a degree d polynomial, computable by a circuit of size s0 in terms of polynomials of degree at
most d/2 + 1, and circuit complexity 3s0 . We have also had to incur an additional additive cost of O(s02 )
for the formula computing R. The idea of the proof is to keep applying this reduction for log d iterations,
such that the degree of each of the polynomials is at most a constant. Then, we compute these generating
polynomials by a formula by brute force.
We now argue that the number of y variables introduced in the process, and the total size of the
formula for the final verifier is still polynomially bounded in s, d. The number of auxiliary y variables
introduced is given by the following recurrence.
m(d, s0 ) ≤ 5s0 + 5m(d/2 + 1, 3s0 ) .
The size of the formula F(d, s) is upper bounded by the following recurrence.
F(d, s0 ) ≤ c · s02 + 5F(d/2 + 1, 3s0 ) ,
where c > 0 is some constant. It is not hard to see that both m(d, s0 ) and F(d, s0 ) are upper bounded by a
fixed polynomial function of d, s0 .
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 29
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
Acknowledgment
We thank Rafael Oliveira for making us aware of the question about the complexity of factors of
polynomials in VNP, and Guy Moshkovitz for helpful discussions.
We also thank the anonymous reviewers at ToC and the editor-in-chief László Babai for various
comments and suggestions which helped improve the readability of this paper.
References
[1] M ANINDRA AGRAWAL AND V. V INAY: Arithmetic circuits: A chasm at depth four. In Proc. 49th
FOCS, pp. 67–75. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.32] 11
[2] V IKRAMAN A RVIND , P USHKAR S. J OGLEKAR , PARTHA M UKHOPADHYAY, AND S. R AJA:
Randomized polynomial-time identity testing for noncommutative circuits. Theory of Computing,
15(7):1–36, 2019. [doi:10.4086/toc.2019.v015a007] 14
[3] WALTER BAUR AND VOLKER S TRASSEN: The complexity of partial derivatives. Theoret. Comput.
Sci., 22(3):317–330, 1983. [doi:10.1016/0304-3975(83)90110-X] 3
[4] P ETER B ÜRGISSER: Completeness and Reduction in Algebraic Complexity Theory. Springer, 2000.
[doi:10.1007/978-3-662-04179-6] 7
[5] P ETER B ÜRGISSER: The complexity of factors of multivariate polynomials. Found. Computational
Math., 4(4):369–396, 2004. Preliminary version in FOCS’01. [doi:10.1007/s10208-002-0059-5] 8
[6] R ICHARD A. D E M ILLO AND R ICHARD J. L IPTON: A probabilistic remark on algebraic program
testing. Information Processing Letters, 7(4):193–195, 1978. [doi:10.1016/0020-0190(78)90067-4]
14
[7] P RANJAL D UTTA , N ITIN S AXENA , AND A MIT S INHABABU: Discovering the roots: Uniform
closure results for algebraic classes under factoring. In Proc. 50th STOC, pp. 1152–1165. ACM
Press, 2018. [doi:10.1145/3188745.3188760, arXiv:1710.03214] 2, 8, 10, 20, 26
[8] Z EEV DVIR , A MIR S HPILKA , AND A MIR Y EHUDAYOFF: Hardness-randomness tradeoffs for
bounded depth arithmetic circuits. SIAM J. Comput., 39(4):1279–1293, 2010. Preliminary version
in STOC’08. [doi:10.1137/080735850] 2, 4, 5, 8, 10, 12, 14, 16, 23, 24
[9] M ICHAEL A. F ORBES: Deterministic divisibility testing via shifted partial derivatives. In Proc.
56th FOCS, pp. 451–465. IEEE Comp. Soc. Press, 2015. [doi:10.1109/FOCS.2015.35] 7
[10] H ERVÉ F OURNIER , N UTAN L IMAYE , G UILLAUME M ALOD , AND S RIKANTH S RINIVASAN:
Lower bounds for depth-4 formulas computing iterated matrix multiplication. SIAM J. Comput.,
44(5):1173–1201, 2015. Preliminary version in STOC’14. [doi:10.1137/140990280] 3, 6
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 30
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
[11] A NKIT G UPTA , P RITISH K AMATH , N EERAJ K AYAL , AND R AMPRASAD S APTHARISHI: Ap-
proaching the chasm at depth four. J. ACM, 61(6):33:1–33:16, 2014. Preliminary version in CCC’13.
[doi:10.1145/2629541] 3, 6
[12] A NKIT G UPTA , P RITISH K AMATH , N EERAJ K AYAL , AND R AMPRASAD S APTHARISHI: Arith-
metic circuits: A chasm at depth 3. SIAM J. Comput., 45(3):1064–1079, 2016. Preliminary version
in FOCS’13. [doi:10.1137/140957123] 9, 11
[13] VALENTINE K ABANETS AND RUSSELL I MPAGLIAZZO: 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] 2, 3, 4, 5, 23
[14] K YRIAKOS K ALORKOTI: A lower bound for the formula size of rational functions. SIAM J.
Comput., 14(3):678–687, 1985. Preliminary version in ICALP’82. [doi:10.1137/0214050] 3
[15] E RICH K ALTOFEN: Polynomial-time reductions from multivariate to bi- and univariate integral
polynomial factorization. SIAM J. Comput., 14(2):469–489, 1985. [doi:10.1137/0214035] 2
[16] E RICH K ALTOFEN: Uniform closure properties of P-computable functions. In Proc. 18th STOC,
pp. 330–337. ACM Press, 1986. [doi:10.1145/12130.12163] 2
[17] E RICH K ALTOFEN: Single-factor Hensel lifting and its application to the straight-line com-
plexity of certain polynomials. In Proc. 19th STOC, pp. 443–452. ACM Press, 1987.
[doi:10.1145/28395.28443] 2
[18] E RICH K ALTOFEN: Factorization of polynomials given by straight-line programs. In Randomness
and Computation, pp. 375–412. JAI Press, 1989. 2, 3, 9
[19] N EERAJ K AYAL , C HANDAN S AHA , AND R AMPRASAD S APTHARISHI: A super-polynomial lower
bound for regular arithmetic formulas. In Proc. 46th STOC, pp. 146–153. ACM Press, 2014.
[doi:10.1145/2591796.2591847] 6
[20] PASCAL KOIRAN: Arithmetic circuits: The chasm at depth four gets wider. Theoret. Comput. Sci.,
448:56–65, 2012. [doi:10.1016/j.tcs.2012.03.041, arXiv:1006.4700] 11
[21] M RINAL K UMAR: A quadratic lower bound for homogeneous algebraic branching programs.
Comput. Complexity, 28(3):409–435, 2019. Preliminary version in CCC’17. [doi:10.1007/s00037-
019-00186-3] 3
[22] M RINAL K UMAR AND R AMPRASAD S APTHARISHI: An exponential lower bound for homo-
geneous depth-5 circuits over finite fields. In Proc. 32nd Computational Complexity Conf.
(CCC’17), volume 79, pp. 31:1–31:30. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017.
[doi:10.4230/LIPIcs.CCC.2017.31, arXiv:1507.00177] 6
[23] M RINAL K UMAR AND S HUBHANGI S ARAF: On the power of homogeneous depth 4 arith-
metic circuits. SIAM J. Comput., 46(1):336–387, 2017. Preliminary version in FOCS’14.
[doi:10.1137/140999335, arXiv:1404.1950] 3, 6
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 31
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
[24] RUDOLF L IDL AND H ARALD N IEDERREITER: Finite Fields. Encyclopedia of Mathematics and its
Applications. Cambridge Univ. Press, 2nd edition, 1996. [doi:10.1017/CBO9780511525926] 32
[25] DAVID E. M ULLER: Application of boolean algebra to switching circuit design and to error
detection. Trans. Inst. Radio Engineers Professional Group on Electronic Computers, EC-3:6–12,
1954. [doi:10.1109/IREPGELC.1954.6499441] 14
[26] N OAM N ISAN: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, 1991.
Preliminary version in FOCS’88. [doi:10.1007/BF01375474] 3, 13
[27] N OAM N ISAN AND AVI W IGDERSON: Hardness vs randomness. J. Comput. System Sci., 49(2):149–
167, 1994. Preliminary version in FOCS’88. [doi:10.1016/S0022-0000(05)80043-1] 3
[28] N OAM N ISAN AND AVI W IGDERSON: Lower bounds on arithmetic circuits via partial
derivatives. Comput. Complexity, 6(3):217–234, 1996. Preliminary version in FOCS’95.
[doi:10.1007/BF01294256] 3, 6
[29] R AFAEL O LIVEIRA: Factors of low individual degree polynomials. Comput. Complexity, 25(2):507–
561, 2016. [doi:10.1007/s00037-016-0130-2] 2, 4, 8, 9, 10, 19, 21, 22
[30] Ø YSTEIN O RE: Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I, 7(15):27, 1922.
Polynomial Identity Lemma cited with full proof in [24, Theorem 6.13]. 14
[31] R AN R AZ: Separation of multilinear circuit and formula size. Theory of Computing, 2(6):121–135,
2006. Preliminary version in FOCS’04. [doi:10.4086/toc.2006.v002a006] 3, 6
[32] R AN R AZ: Elusive functions and lower bounds for arithmetic circuits. Theory of Computing,
6(7):135–177, 2010. Preliminary version in STOC’08. [doi:10.4086/toc.2010.v006a007] 3, 6
[33] R AN R AZ: Tensor-rank and lower bounds for arithmetic formulas. J. ACM, 60(6):40:1–40:15, 2013.
Preliminary version in STOC’10. [doi:10.1145/2535928] 6
[34] R AN R AZ , A MIR S HPILKA , AND A MIR Y EHUDAYOFF: A lower bound for the size of syntactically
multilinear arithmetic circuits. SIAM J. Comput., 38(4):1624–1647, 2008. Preliminary version in
FOCS’07. [doi:10.1137/070707932] 3
[35] R AN R AZ AND A MIR Y EHUDAYOFF: Lower bounds and separations for constant depth mul-
tilinear circuits. Comput. Complexity, 18(2):171–207, 2009. Preliminary version in CCC’08.
[doi:10.1007/s00037-009-0270-8] 3, 6
[36] W OLFGANG M. S CHMIDT: Equations over Finite Fields: An Elementary Approach. Volume 536
of Lecture Notes in Math. Springer, 1st edition, 1976. 14
[37] JACOB T. S CHWARTZ: Fast probabilistic algorithms for verification of polynomial identi-
ties. Journal of the ACM, 27(4):701–717, 1980. Preliminary version in EUROSAM’79.
[doi:10.1145/322217.322225] 14
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 32
C LOSURE R ESULTS FOR P OLYNOMIAL FACTORIZATION
[38] A MIR S HPILKA AND A MIR Y EHUDAYOFF: Arithmetic circuits: A survey of recent results and open
questions. Found. and Trends Theor. Comput. Sci., 5:207–388, 2010. [doi:10.1561/0400000039] 4
[39] S ÉBASTIEN TAVENAS: Improved bounds for reduction to depth 4 and depth 3. Inform. and Comput.,
240:2–11, 2015. Preliminary version in MFCS’13. [doi:10.1016/j.ic.2014.09.004, arXiv:1304.5777]
11
[40] L ESLIE G. VALIANT: Reducibility by algebraic projections. In Logic and Algorithmic, volume 28
of L’Enseignement Mathématique, pp. 253–268. 1982. 9, 25, 26
[41] L ESLIE G. VALIANT, S VEN S KYUM , S TUART J. B ERKOWITZ , AND C HARLES R ACKOFF: Fast
parallel computation of polynomials using few processors. SIAM J. Comput., 12(4):641–644, 1983.
Preliminary version in MFCS’81. [doi:10.1137/0212043] 10, 12, 25
[42] R ICHARD E. Z IPPEL: Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic
Comput. (EUROSAM’79), volume 72 of LNCS, pp. 216–226. Springer, 1979. [doi:10.1007/3-540-
09519-5_73] 14
AUTHORS
Chi-Ning Chou
Ph. D. student
School of Engineering and Applied Sciences
Harvard University
Cambridge, Massachusetts, USA
cnchou g harvard edu
http://cnchou.github.io/
Mrinal Kumar
Postdoctoral fellow
Department of Computer Science
University of Toronto
Toronto, Ontario, Canada
mrinalkumar08 gmail com
http://mrinalkr.bitbucket.io/
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 33
C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON
Noam Solomon
Postdoctoral researcher
Department of Mathematics
Massachusetts Institute of Technology
Cambridge, Massachusetts, USA
noam.solom gmail com
https://sites.google.com/site/noamsolomonswebpage/home/
ABOUT THE AUTHORS
C HI -N ING C HOU is a Ph. D. student in the Theory of Computation group at Harvard
University, where he is advised by Boaz Barak. He received a B. S. from National
Taiwan University in 2016 and worked as a research assistant in Academia Sinica for one
year, mentored by Kai-Min Chung, who not only showed him how to be an independent
researcher but also gave him lots of freedom to explore. His research interests include
computational complexity, algebraic complexity, cryptography, quantum computing,
and their intersections with other fields. Outside academics, he loves playing baseball,
playing Go, listening to classical music, and cooking.
M RINAL K UMAR is a postdoc in the Theory group at the University of Toronto, where
his host is Ben Rossman. Prior to this, he was a research fellow in the Program on
Lower Bounds in Computational Complexity at the Simons Institute for the Theory of
Computing, Berkeley, CA, and a postdoc in the Combinatorics and Complexity Program
at the Center for Mathematical Sciences and Applications at Harvard. He received his
Ph. D. in Computer Science in May 2017 from Rutgers University where he was advised
by Swastik Kopparty and Shubhangi Saraf. His research interests are in arithmetic and
Boolean circuit complexity and error correcting codes. Mrinal spent his undergrad years
at IIT Madras and owes his interest in Complexity Theory to a delightful class on the
topic taught by Jayalal Sarma. Apart from theory, he finds great joy in test cricket and in
the adventures of Calvin & Hobbes.
N OAM S OLOMON is a postdoc at the Mathematics department at MIT, and before that he
was a postdoc at the Center for Mathematical Sciences and Applications at Harvard
University. He holds a Ph. D. in Computer-Science from Tel-Aviv University and a
Ph. D. in Number Theory from Ben-Gurion University. His research interests include
combinatorial and computational geometry, combinatorics, algebraic complexity and
number theory. Outside research, he enjoys sports, music, books, a good movie once in a
while, and socializing.
T HEORY OF C OMPUTING, Volume 15 (13), 2019, pp. 1–34 34