Authors Zeyu Guo, Nitin Saxena, Amit Sinhababu,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30
www.theoryofcomputing.org
S PECIAL ISSUE : CCC 2018
Algebraic Dependencies and PSPACE
Algorithms in Approximative Complexity
over Any Field
Zeyu Guo∗ Nitin Saxena† Amit Sinhababu‡
Received June 30, 2018; Revised June 16, 2019; Published December 14, 2019
Abstract: Testing whether a set f of polynomials has an algebraic dependence is a basic
problem with several applications. The polynomials are given as algebraic circuits. The
complexity of algebraic independence testing is wide open over finite fields (Dvir, Gabizon,
Wigderson, FOCS’07). Previously, the best complexity bound known was NP#P (Mittmann,
Saxena, Scheiblechner, Trans. AMS 2014). In this article we put the problem in AM ∩ coAM.
In particular, dependence testing is unlikely to be NP-hard. Our proof uses methods of
algebraic geometry. We estimate the size of the image and the sizes of the preimages of
the polynomial map f over the finite field. A gap between the corresponding sizes for
independent and for dependent sets of polynomials is utilized in the AM protocols.
A conference version of this paper appeared in the Proceedings of the 33rd Computational Complexity Conference
(CCC’18) [24] and as a poster in STOC 2018: TheoryFest.
∗ Supported by DST and Research I Foundation of CSE, IITK.
† Supported by DST/SJF/MSA-01/2013-14.
‡ Supported by DFG grant TH 472/5-1.
ACM Classification: I.1, F.2.1, F.1.3, G.1.2
AMS Classification: 03D15, 14Q20
Key words and phrases: algebraic dependence, Jacobian, Arthur-Merlin, approximate polynomial,
satisfiability, hitting set, border VP, finite field, PSPACE, EXPSPACE, GCT Chasm, Polynomial Identity
Lemma
© 2019 Zeyu Guo, Nitin Saxena, and Amit Sinhababu
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2019.v015a016
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
Next, we study the open question of testing whether every annihilator of f has zero
constant term (Kayal, CCC’09). We introduce a new problem called approximate polynomial
satisfiability (APS), which is equivalent to the preceding question by a classical character-
ization in terms of the Zariski closure of the image of f. We show that APS is NP-hard
and, using ideas from algebraic geometry, we put APS in PSPACE. (The best previous
bound was EXPSPACE via Gröbner basis computation.) As an unexpected application
of this to approximative complexity theory we obtain that, over any field, hitting sets for
VP can be constructed in PSPACE. This solves an open problem posed in (Mulmuley,
FOCS’12, J. AMS 2017), greatly mitigating the GCT Chasm (exponentially in terms of space
complexity).
1 Introduction
Algebraic dependence is a generalization of linear dependence. Polynomials f1 , . . . , fm ∈ F[x1 , . . . , xn ] are
called algebraically dependent over the field F if there exists a nonzero polynomial (called annihilator)
A(y1 , . . . , ym ) ∈ F[y1 , . . . , ym ] such that A( f1 , . . . , fm ) = 0. If no A exists, then the given polynomials are
called algebraically independent over F. The transcendence degree (trdeg) of a set of polynomials is
the analog of rank in linear algebra. It is defined as the maximum number of algebraically independent
polynomials in the set. Both algebraic dependence and linear dependence define matroid structures [20].
There exist algebraic matroids over F p that are not linear [28].
The simplest example of algebraically independent polynomials is x1 , . . . , xn ∈ F[x1 , . . ., xn ]. As an
example of algebraically dependent polynomials, we can take f1 = x, f2 = y and f3 = x2 + y2 . Then,
y21 +y22 −y3 is an annihilator. The underlying field is crucial in this concept. For example, for a given prime
number p, the polynomials x + y and x p + y p are algebraically dependent over fields of characteristic p (as
(x + y) p = x p + y p in characteristic p). But they are algebraically independent over fields of characteristic
zero (e. g., Q) and over fields of positive characteristic ` 6= p.1
Thus, the following computational question, AD(F), is natural and it is the first problem we consider
in this paper: Given polynomials f1 , . . . , fm ∈ F[x1 , . . . , xn ], represented as algebraic circuits, test if they are
algebraically dependent. It can be solved in PSPACE using a classical result due to Perron [48, 49]. We
sketch the proof of this result here: Perron proved that given a set of algebraically dependent polynomials,
there exists an annihilator whose degree is at most the product of the degrees of the polynomials in
the set. (This exponential degree bound is tight [30].) It is not hard to see that testing the existence
of such an annihilator reduces to solving a system of linear equations in exponentially many variables
where the coefficients of the annihilator are regarded as the variables of the system. It is also known
that solving a system of linear equations is in logspace-uniform NC [15, 9, 43], which is contained in
PolyL (polylogarithmic space). Combining these results we see that testing algebraic dependence (and
computing an annihilator polynomial) is in PSPACE.
Computing the annihilator may be quite hard, but it turns out that the decision version is easy over
zero (or large) characteristic using a classical result known as the Jacobian criterion [29, 7]. The Jacobian
efficiently reduces algebraic dependence testing of f1 , . . . , fm over F to linear dependence testing of the
1 This can be seen using the Jacobian criterion [29, 7] as discussed below.
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 2
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
differentials d f1 , . . . , d fm over F(x1 , . . . , xn ), where we view d fi as the vector
∂ fi ∂ fi
,..., .
∂ x1 ∂ xn
Placing d fi as the i-th row gives us the Jacobian matrix J of f1 , . . . , fm . If the characteristic of the field
F is zero (or larger than the product of the degrees deg( fi )) then the transcendence degree of f1 , . . . , fm
equals rank(J). It follows from the Polynomial Identity Lemma2 that, with high probability, rank(J) is
equal to the rank of J evaluated at a random point in Fn . This gives a simple randomized polynomial-time
algorithm solving AD(F), over the fields F satisfying the condition stated above.
For fields of positive characteristic, if the polynomials are algebraically dependent, then their Jacobian
matrix is not full rank. But the converse is not true. There are infinitely many input instances (set
of algebraically independent polynomials) for which the Jacobian criterion fails. The failure can be
characterized by the notion of “inseparable extension” [47]. For example, x p , yp are algebraically
independent over F p , yet their Jacobian determinant vanishes. Another example is, x p−1 y, xy p−1 over
F p for prime p > 2. Mittmann, Saxena, and Scheiblechner [41] gave a criterion, called Witt-Jacobian,
that works over fields of positive characteristic, improving the complexity of algebraic independence
testing from PSPACE to NP#P . [47] gave another generalization of the Jacobian criterion that is efficient
in special cases.
Given that an efficient algorithm to tackle positive characteristic is not in close sight, one could
speculate the problem to be NP-hard or even outside the polynomial hierarchy PH. In the present article
we show that for finite fields, AD(F) is in AM ∩ coAM (Theorem 1.1). This rules out the possibility
of NP-hardness, unless the polynomial-time hierarchy collapses [4]. Thus, AD(F) joins the league of
problems of “intermediate” complexity, such as graph isomorphism and integer factoring.
Constant term of the annihilators. We come to the second problem AnnAtZero that we discuss in
this paper: Testing if the constant term of every annihilator of a set of polynomials (given as algebraic
circuits), f = { f1 , . . . , fm }, is zero. The annihilators of f constitute a prime ideal of the polynomial ring
F[y1 , . . . , ym ]. This ideal is principal when the transcendence degree of f is m − 1. This is a classical result
in commutative algebra [39, Theorem 47]. See also [30, Lemma 7] for an exposition. In this case, we can
decide in PSPACE if the constant term of the minimal annihilator is zero, as the unique annihilator (up to
scaling) can be computed in PSPACE.
If the transcendence degree of f is less than m − 1, the ideal of the annihilators of f is no longer
principal. Although the ideal is finitely generated, finding the generators of this ideal is computationally
very hard. (E. g., using Gröbner basis techniques, we can do it in EXPSPACE [17, Section 1.2.1].) In
this case, can we decide if all the annihilators of f have constant term zero? We give two equivalent
characterizations of AnnAtZero—one geometric and the other algebraic—and we use them to devise a
PSPACE algorithm to solve it in all cases (Theorem 1.3).
Interestingly, there is an application of the above algorithm to algebraic complexity. We give a
PSPACE-explicit construction of a hitting set of the class VPFq (Theorem 1.4). VPFq consists of n-variate
2 Regarding the Polynomial Identity Lemma, the following footnote appears in [14]. “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 [46, 42, 56, 16, 60, 57]. For a brief history, see [5] where the term
“Polynomial Identity Lemma” is attributed to L. Babai.”
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 3
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
polynomials of degree d = nO(1) over the field Fq , that can be “infinitesimally approximated” by algebraic
circuits of size s = nO(1) . A polynomial p(x1 , . . . , xn ) over an algebraically closed field F is said to be
infinitesimally approximated by a circuit of size s, if the circuit computes a polynomial of the form
p + ε p1 + ε 2 p2 + · · · + ε m pm , where the circuit uses constants from F(ε) (for example, 1/ε can be used
as a constant) and p1 , . . . , pm ∈ F[x1 , . . . , xn ].
A set H of points is called a hitting set for a set C of polynomials, if any nonzero polynomial in C
evaluates to a nonzero value in at least one point in H. It was shown by Heintz and Schnorr [27] that
hitting sets of size poly(n, s) and bit length poly(n, s, log d) exist for the class of n-variate polynomials of
degree at most d computed by size s arithmetic circuits. The same result extends to the class of n-variate
polynomials of degree at most d infinitesimally approximated by size s arithmetic circuits. Now the
problem of constructing explicit hitting sets for VP asks to deterministically compute a set of points that
is a hitting set for the class of n-variate polynomials of degree at most d, infinitesimally approximated by
size s arithmetic circuits.
The above problem is interesting as natural questions like explicit construction of the normalization
map (in Noether’s Normalization Lemma NNL) reduce to the construction of a hitting set of VP (Mul-
muley [45]), which was previously known to be only in EXPSPACE [45, 44]. This was recently put in
PSPACE, over the field C, by Forbes and Shpilka [21]. Their proof uses real analysis and does not apply
to finite fields. We need to develop purely algebraic concepts to solve the finite field case (namely through
AnnAtZero), which apply to any field.
To further motivate the concept of algebraic dependence, we list a few recent problems in computer
science. The first problem is about constructing an explicit randomness extractor for sources which
are polynomial maps over finite fields. Using the Jacobian criterion, [19, 18] solved the problem for
fields with large characteristic. The second application is to the famous polynomial identity testing
(PIT) problem. To efficiently design hitting sets, for some interesting models, [7, 3, 34] constructed a
family of trdeg-preserving maps. For more background and applications of algebraic dependence testing,
see [47]. The annihilator has been a key concept to prove the connection between hitting sets and lower
bounds [27], and in bootstrapping “weak” hitting sets [2].
Finally, we remark that a common thread among the problems we study in this paper is studying
the closure of the polynomial map. Let f : Fn → Fn be a given polynomial map. Then, we study two
computational questions: (1) (Algebraic Dependence Testing) whether the dimension of the Zariski
closure of the image of f is < n? (2) (Origin in closure) whether the origin 0 is in the Zariski closure of
the image of f ?
1.1 Our results
In this paper, we give Arthur-Merlin protocols and algorithms, with proofs using basic tools from algebraic
geometry. The first theorem we prove is about AD(Fq ) .
Theorem 1.1. Testing algebraic independence of multivariate polynomials over a finite field is in
AM ∩ coAM.
This result vastly improves the current best upper bound known for AD(Fq )—from being “outside”
the polynomial hierarchy (namely NP#P [41]) to “lower” than the second level of the polynomial hierarchy
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 4
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
(namely AM ∩ coAM). This rules out the possibility of AD(Fq ) being NP-hard (unless the polynomial
hierarchy collapses to the second level [4]). Recall that, for a field F of characteristic zero or of large
characteristic, AD(F) is in coRP (Section 2). We conjecture such a result for AD(Fq ) too.
Our second result is about the problem AnnAtZero (i. e., testing whether all the annihilators of given
f have constant term zero). A priori it is unclear why it should have complexity better than EXPSPACE.
(Note: ideal membership is EXPSPACE-complete [40].)
First, we relate the problem AnnAtZero to a (new) version of polynomial system satisfiability, over
the algebraic closure F.
Problem 1.2 (Approximate polynomials satisfiability (APS)). Given polynomials
f1 , . . . , fm ∈ F[x1 , . . . , xn ] ,
represented as algebraic circuits, does there exist β ∈ F(ε)n such that for all i, fi (β ) is in the ideal εF[ε]
of F[ε]? If yes, then we say that f := { f1 , . . . , fm } is in APS.
It is easy to show that the function field F(ε) here can be equivalently replaced by the ring F[ε, ε −1 ]
of Laurent polynomials, or, the field F((ε)) of formal Laurent series (use mod εF[ε]). A reason why
these objects appear in algebraic complexity can be found in [11, Section 5.2] and [37, Section 5]. They
help algebrize the notion of “infinitesimal approximation” (in real analysis think of ε → 0 & 1/ε → ∞).
A notable computational issue involved is that the degree bound of ε required for β is exponential in the
input size [37, Proposition 3]; this may again be a “justification” why APS may require that much space.
n
Classically, the exact version of APS has been well-studied—Does there exist β ∈ F such that for
all i, fi (β ) = 0? This is what Hilbert’s Nullstellensatz (HN) characterizes. HN also yields an impressive
PSPACE algorithm [32, 33]. Note that if system f has an exact solution, then it is trivially in APS. But
the converse is not true. For example, {x, xy − 1} is in APS, but there is no exact solution in F. To see that
it is in APS, assign x = ε and y = 1/ε. Also, the instance {x, x + 1} is neither in APS nor does it have an
exact solution. Finally, note that if we restrict β to come from F[ε]n then APS becomes equivalent to
exact satisfiability and HN applies. This can be seen by going modulo εF[ε], as the quotient F[ε]/εF[ε]
is F.
Coming back to AnnAtZero, we show that it is equivalent both to a geometric question and to deciding
APS. This gives us, with more work, the following surprising consequence.
Theorem 1.3. APS is NP-hard and is in PSPACE.
We apply this to designing hitting sets and solving NNL. (We refer to [45] for the background.)
Theorem 1.4. There is a PSPACE algorithm that (given input n, s, r in unary and suitably large q in
binary) computes a set of points from Fnq of size poly(n, s) that hits all n-variate degree-r polynomials
over Fq that can be infinitesimally approximated by size-s circuits.
To state the results on NNL, we need the following notation from [45]. Let m be a positive integer
and r = m2 . Let V be the vector space of homogeneous degree-m polynomials in the variables x1 , . . . , xr
over an algebraically closed field F. Each f ∈ V determines a point [ f ] in the projective space PV . Let
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 5
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
Σ[det, m] be the set of points [ f ] such that f is a symbolic determinant of a matrix M ∈ Fm×m whose
entries are linear forms in x1 , . . . , xr . Finally, let ∆[det, m] ⊆ PV be the Zariski closure of Σ[det, m].
Mulmuley [45] considers the problem of constructing a homogeneous linear map that maps Σ[det, m] ⊆
PV to a much smaller projective space Pk (a normalizing map). In particular, we want to compute a
set S = {p0 , . . . , pk } in poly(m)-time, where k = poly(m) and pi ∈ Fr for i ∈ [k], such that the map
f 7→ ( f (p0 ), . . . , f (pk )) induces a well-defined map from Σ[det, m] to Pk . Such a set S is called a (strict)
e.s.o.p. (explicit system of parameters). In addition, an e.s.o.p. S is separating if for any distinct f , g
satisfying [ f ], [g] ∈ ∆[det, m], we have f (pi ) 6= g(pi ) for some pi ∈ S.
As shown in [45], the problem of constructing a separating e.s.o.p. reduces to that of constructing hit-
ting sets for VP [45, Theorem 4.5]. Combining this reduction with our PSPACE algorithm of constructing
hitting sets for VP, we obtain the following result.
Theorem 1.5 (NNL for ∆[det, m] in PSPACE). The problem of constructing a separating e.s.o.p. for
∆[det, m] belongs to PSPACE.
The results for ∆[det, m] also hold for other varieties, as long as such varieties satisfy some explicitness
condition. This is captured by the notion of an explicit family {Wn } of varieties in [45]. See [45,
Definition 5.1] for the formal definition. For such varieties Wn , constructing a separating e.s.o.p. also
reduces to constructing hitting sets for VP [45, Theorem 5.11]. So we have the following result.
Theorem 1.6 (NNL for explicit varieties in PSPACE). Let {Wn } be an explicit family of varieties as
in [45, Definition 5.1]. Then the problem of constructing a separating e.s.o.p. for Wn belongs to PSPACE.
More applications? The exact polynomials satisfiability question HN (over F) is highly expressive and,
naturally, many computational problems can be expressed that way. We claim that in a similar spirit,
the APS question expresses those computer science problems that involve “infinitesimal approximation.”
Since finite fields do not have a topology allowing approximations, algebraic approximations over
arbitrary fields are needed. The latter has been useful in fast matrix multiplication algorithms.
One prominent example of algebraic approximation is the concept of border rank of tensor polynomi-
als (used in matrix multiplication algorithms and Geometric Complexity Theory (GCT), see [12, 35, 36]).
Border rank computation of a given tensor (over F) can easily be reduced to an APS instance and, hence,
now solved in PSPACE. This brings the complexity of border rank closer to the complexity of tensor
rank [54]. From the point of view of Gröbner basis theory, APS is a problem that seems a priori much
harder than HN. Now that both of them have a PSPACE algorithm, one may wonder whether it can
be brought all the way down to NP or AM? (In fact, HNC is known to be in AM, conditionally under
GRH [32].)
More generally, APS is naturally related to GCT as follows. The program of GCT aims to find an
explicit hard polynomial g (e. g., the permanent) in a vector space V ⊆ F[x1 , . . . , xn ] and prove that its
projective image [g] ∈ PV is not contained in a certain projective variety X that consists of the “easy”
polynomials. The affine cone X̂ ⊆ V of X is often specified as the Zariski closure of the image of some
morphism f from an affine space (see, e. g., [50, Section 2] for the case that X is a higher secant variety of
a Segre–Veronese variety). The problem then becomes proving g 6∈ X̂ = Im(f), or equivalently, proving
0 6∈ Im(f0 ), where 0 is the origin of V and f0 is the translation of f by −g. As we will see in this paper, one
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 6
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
equivalent formulation of APS is precisely the problem of deciding if 0 is in the Zariski closure of the
image of a given morphism from an affine space.
Our methods in the proof of Theorem 1.3 also imply an interesting “degree bound” related to the
√
(prime) ideal I of annihilators of the set f of polynomials. Namely, I = I≤d , where I≤d refers to the
subideal generated by degree ≤ d polynomials in I, d is the Perron-like bound (maxi∈[m] deg( fi ))k , and
k := trdeg(f). This is equivalent to the geometric fact, which we prove, that the varieties defined by the
two ideals I and I≤d are equal (Theorem 4.6). This again is an exponential improvement over what one
expects to get from the general Gröbner basis methods, because, the generators of I may well have doubly
exponential degree.
The result on hitting set (Theorem 1.4) can be applied to compute, in PSPACE, the explicit system of
parameters (e.s.o.p.) of the invariant ring of the variety ∆[det, s], over Fq , with a given group action [45,
Theorem 4.9]. Also, we can now construct, in PSPACE, polynomials in Fq [x1 , . . . , xn ] that cannot even
be approximated by “small” algebraic circuits. Such results were previously known only for fields of
characteristic zero, see [21, Theorems 1.1–1.4]. Bringing this complexity down to P is the longstanding
problem of blackbox PIT (and lower bounds), see [52, 58, 53]. Mulmuley [44] pointed out that small
hitting sets for VP can be designed in EXPSPACE which is a far worse complexity than that for VP. He
called it the GCT Chasm. We bridge it somewhat, as the proof of Theorem 1.4 shows that small hitting
sets for VPF can be designed in PSPACE (like those for VP) for any field F.
In another application, the null-cone problem defined in [13] can be seen as a special case of APS
and using our algorithm, it can be solved in PSPACE. Bürgisser et al. [13] gave an exponential-time
algorithm for the above problem (bringing it down from EXPSPACE).
Finally, another motivation for AnnAtZero or APS comes from the study of the geometric ideal proof
system in algebraic proof complexity, introduced in [23], where they essentially discuss AnnAtZero for
systems of polynomial equations corresponding to Boolean tautologies. See [23, Appendix B] for more
details.
Remark 1.7. Given a system of polynomial equations f1 (x1 , . . . , xn ) = 0, . . . , fm (x1 , . . . , xn ) = 0, we can
always homogenize the fi by introducing a new variable z. The question of projective polynomials
satisfiability for a given system of equations is whether there is a nonzero solution (called a projective
solution) to the homogenized system. We have seen that APS does not directly reduce to (affine)
polynomials satisfiability, as there are unsatisfiable systems, e. g., {X = 0, XY = 1}, that have approximate
solutions. We note that APS does not directly reduce to projective polynomials satisfiability either.
Consider, for example, the system {X +Y = 0, X +Y = 1}, corresponding to two parallel affine lines.
It has no approximate solution, but the homogenized system {X +Y = 0, X +Y = Z} has a projective
solution (1, −1, 0).
Nonetheless, it is true that if the equations f1 = 0, . . . , fm = 0 have an approximate solution, then
the homogenized equations fˆ1 = 0, . . . , fˆm = 0 have a projective solution (in Pn ). We sketch a proof of
this fact. Suppose a1 , . . . , an ∈ F(ε) ⊆ F((ε)) form an approximate solution of the original system. Let
an+1 = 1. Then fi (a1 , . . . , an ) = fˆi (a1 , . . . , an , an+1 ) for i ∈ [m]. Choose the smallest k ∈ Z such that ε k ai
is in the ring of formal power series F[[ε]] for all i ∈ [n + 1]. We have k ≥ 0 as an+1 = 1. For i ∈ [n + 1], let
āi ∈ F be the constant term of ε k ai . Minimality of k guarantees that āi 6= 0 for some i ∈ [n + 1]. Assigning
ā1 , . . . , ān+1 to x1 , . . . , xn , z then gives a projective solution to the equations fˆ1 = 0, . . . , fˆm = 0.
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 7
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
1.2 Proof ideas
Proof idea of Theorem 1.1. Suppose we are given polynomials (represented as algebraic circuits)
f := { f1 , . . . , fm } computing in Fq [x1 , . . . , xn ]. For the AM and coAM protocols, we consider the following
system of equations over a “small” extension Fq0 .
For b = (b1 , . . . , bm ) ∈ Fm
q0 , define the system of equations f i (x1 , . . . , xn ) = bi , for i ∈ [m]. We denote
the number of solutions of the above system in Fnq0 as Nb . Let f : Fnq0 → Fm q0 be the polynomial map
a 7→ ( f1 (a), . . . , fm (a)).
AM gap. [Theorem 3.5] We establish bounds for the number N f (a) , where a is a random point in Fnq0 .
If f1 , . . . , fm are independent, we show that N f (a) is relatively small. On the other hand, if the polynomials
are algebraically dependent then N f (a) is much greater.
Assume f is algebraically independent. Without loss of generality [47, Section 2] we can assume that
m = n and for all i ∈ [n], xi , f1 , . . . , fn are algebraically dependent. The first step is to show that with high
probability, the zero set defined by the system of equations, for random f (a), is finite (i. e., it has dimension
≤ 0 as a variety). This is proved using the Perron degree bound on the annihilator of {xi , f1 , . . . , fn }. Next,
one can apply an affine version of Bézout’s theorem to obtain an upper bound on N f (a) . On the other
hand, suppose f is algebraically dependent, say with annihilator Q. Let Im( f ) := f (Fnq0 ) be the image of
f . Since Q vanishes on Im( f ), we know that Im( f ) is relatively small, whence we deduce that N f (a) is
large for “most” values of a.
coAM gap. [Theorem 3.8] We pick a random point b = (b1 , . . . , bm ) ∈ Fm q0 and bound Nb , which is the
number of solutions of the system defined above. In the dependent case, we show that Nb = 0 for “most”
values of b. But in the independent case, we show that Nb ≥ 1 for “many” (maybe not “most”!) values of
b. The ideas are based on those sketched above.
The two kinds of gaps shown above are based on the sets f −1 ( f (x)) and Im( f ), resp.
Note that membership in either of these sets is testable in NP (the latter requires nondeterminism).
Based on this and the gaps between the respective cardinalities, we can invoke Lemma 2.1 and devise the
AM and coAM protocols for AD(Fq0 ), which also apply to AD(Fq ).
Remark 1.8. Our proof of Theorem 1.1 employs the fact that we could efficiently sample a random
point in the set Im( f ). In contrast, it is not clear how to efficiently sample a random point in the zero
set Zer(f) := {x ∈ Fnq0 | f (x) = 0}. Thus, we manage to side-step the NP-hardness associated with most
zero set properties. E. g., computing the dimension of Zer(f) is NP-hard.
Proof idea of Theorem 1.3. Let polynomials f := { f1 , . . . , fm } in F[x1 , . . . , xn ] be given over a field F,
represented by algebraic circuits. We want to determine if the constant term of every annihilator for f is
n m
zero. Redefine the polynomial map f : F → F ; a 7→ ( f1 (a), . . . , fm (a)). For a subset S of an affine or
projective space, write S for its Zariski closure in that space, i. e., for the smallest subset that contains S
and equals the zero set Zer(I) of some polynomial ideal I (homogeneous ideal in the projective case).
APS vs. AnnAtZero. [Theorem 4.2] Now, we interpret the problem AnnAtZero in a geometric way
through Lemma 4.1:
The constant term of every annihilator of f is zero iff the origin point 0 ∈ Im( f ).
This has a simple proof using the ideal-variety correspondence [25]. Note that the stronger condition
0 ∈ Im( f ) is equivalent to the existence of a common solution to the equations fi (x1 , . . . , xn ) = 0,
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 8
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
i = 1, . . . , m. The latter problem (call it HN for Hilbert’s Nullstellensatz) is known to be in AM if F = Q
and GRH is assumed [32]. However, Im( f ) is not necessarily Zariski closed; equivalently, it may be
strictly smaller than Im( f ). So, we need new ideas to test 0 ∈ Im( f ).
n
Next, we observe that although 0 ∈ Im( f ) is not equivalent to the existence of a solution x ∈ F to
f (x) = 0, it is equivalent to the existence of an “approximate solution” x ∈ F(ε)n , which is an n-tuple of
rational functions in a formal variable ε. The proof idea of this uses a degree bound on ε due to [37].
We called this problem APS. As AnnAtZero problem is already known to be NP-hard [30], APS is also
NP-hard.
Upper bound on APS. We now know that solving APS for f is equivalent to solving AnnAtZero for f.
AnnAtZero was previously known to be in PSPACE in the special case when the transcendence degree k
of F(f)/F equals m or m − 1, but the general case remained open (best being EXPSPACE).
In this article we prove that AnnAtZero is in PSPACE even when k < m − 1. Our simple idea is
to reduce the input to a smaller m = k + 1 instance, by choosing new polynomials g1 , . . . , gk+1 that
are random linear combinations of the polynomials fi . We show that with high probability, replacing
{ f1 , . . . , fm } by {g1 , . . . , gk+1 } preserves YES/NO instances as well as the transcendence degree. This
gives a randomized poly-time reduction from the case k < m − 1 to k = m − 1 (Theorem 4.6). The latter
has a standard PSPACE algorithm.
For notational convenience view F as the affine line A. Define V := Im( f ) ⊆ Am . Proving that the
above reduction (of m) does preserve YES/NO instances amounts to proving the following geometric
statement: If V does not contain the origin O ∈ Am , then with high probability, the variety V 0 := π(V )
does not contain the origin O0 ∈ Ak+1 either, where π : Am → Ak+1 is a random linear map.
As π is picked at random, the kernel W of π is a random linear subspace of Am . We have O0 6∈ π(V )
whenever V ∩W = 0, / but this is not sufficient for proving O0 6∈ π(V ), since V may “get arbitrarily close
to W ” in Am and meet W “at infinity.”
Example 1. The hyperbola V := V (X1 X2 − 1) and the line W := V (X1 ) do not meet in the affine space A2 ,
even though they get closer and closer as we increase the absolute value of the coordinate X2 . However,
note that the projective closures of these two varieties Vc := V (X1 X2 − X02 ) and Wc := V (X1 ) do meet at
the point (0, 0, 1) of the projective space P2 , which is thought of as one of the “points at infinity.”
Inspired by the above observation, we consider projective geometry instead of affine geometry, and
prove that O0 6∈ V 0 holds as long as the projective closure of V and that of W are disjoint. The proof uses
a construction of a projective subvariety—the join—to characterize π −1 (V 0 ), and eventually rules out
W ⊆ π −1 (V 0 ) (Lemma 4.8).
Moreover, we show that this holds with high probability if O 6∈ V , by (repeatedly) using the fact that
a general (=random) hyperplane section reduces the dimension of a variety by one.
Proof idea of Theorem 1.4. Define A := Fq and assume w.l.o.g. q ≥ Ω(sr2 ) [1]. [27, Theorem 4.4]
showed that a hitting set, of size h := O(s2 n2 ) in Fnq , exists for the class of degree-r polynomials, in
A[x1 , . . . , xn ], that can be infinitesimally approximated by size-s algebraic circuits. So, we can search over
all possible subsets of size h from Fnq and “most” of them are hitting sets.
How do we certify that a candidate set H is a hitting set? The idea is to use universal circuits.
A universal circuit has n essential variables x = {x1 , . . . , xn } and s0 := O(sr4 ) auxiliary variables y =
{y1 , . . . , ys0 }. We can fix the auxiliary variables, from A(ε), in such a way so that it can output any
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 9
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
homogeneous circuit of size-s, approximating a degree-r polynomial in VPA . Given a universal circuit Ψ,
certification of a hitting set H is based on the following observation, that follows from the definitions:
A candidate set H =: {v1 , . . . , vh } is a hitting set iff
0
∀y ∈ A(ε)s , Ψ(y, x) ∈
/ εA[ε][x] ⇒ ∃i ∈ [h], Ψ(y, vi ) ∈
/ εA[ε].
Equivalently, a candidate set H = {v1 , . . . , vh } is not a hitting set iff
0
∃y ∈ A(ε)s , Ψ(y, x) ∈
/ εA[ε][x] and ∀i ∈ [h], Ψ(y, vi ) ∈ εA[ε] .
Note that certification of hitting set is more challenging than the one against polynomials in VP,
because the degree bounds for ε are exponentially high and moreover, we do not know how to frame the
first “non-containment” condition as an APS instance. To translate it to an APS instance, our key idea is
the following.
Pick q ≥ Ω(s0 r2 ) so that a hitting set exists, in Fnq , that works against polynomials infinitesimally
0
approximated by the specializations of Ψ. Suppose Ψ(α, x) is not in εA[ε][x], for some α ∈ A(ε)s .
This means that we can write it as ∑−m≤i≤m0 ε i gi (x) with g−m 6= 0 and m ≥ 0. Clearly, ε m · Ψ(α, x)
infinitesimally approximates the nonzero polynomial g−m ∈ A[x]. By the conditions on Ψ, we know that
g−m is a homogeneous polynomial of degree r (and approximative complexity s0 ). Thus, by Lemma 2.2,
there exists a β ∈ Fnq such that g−m (β ) =: a is a nonzero element in A. We can normalize by this and
consider a−1 ε m · Ψ(y, x), which evaluates to 1 + εA[ε] at (α, β ). Since this normalization factor only
affects the auxiliary variables y, we get another equivalent criterion:
0
A candidate set H = {v1 , . . . , vh } is not a hitting set iff ∃y ∈ A(ε)s and ∃x ∈ Fnq such that,
Ψ(y, x) − 1 ∈ εA[ε] and ∀i ∈ [h], Ψ(y, vi ) ∈ εA[ε].
We reach closer to APS, but how do we implement ∃?x ∈ Fnq (it takes exponential space)?
The idea is to rewrite it, instead using the (r + 1)-th roots of unity Zr+1 ⊆ A, as ∃x ∈ A(ε)n , ∀i ∈ [n],
r+1
xi − 1 ∈ εA[ε]. This gives us a criterion that is an instance of APS with n + h + 1 input polynomials
(Theorem 5.2). By Theorem 1.3 it can be done in PSPACE, finishing the proof. Moreover, this PSPACE
algorithm is independent of the characteristic of the underlying field. (E. g., it can be seen as an alternative
to [21] over the complex field.)
2 Preliminaries
Jacobian. Although this work would not need it, we define the classical Jacobian: Given polynomials f =
{ f1 , · · · , fm } in F[x1 , · · · , xn ], the Jacobian of f is the matrix Jx (f) := (∂x j fi )m×n , where ∂x j fi := ∂ fi /∂ x j .
The Jacobian criterion [29, 7] states that for degree ≤ d and trdeg ≤ r polynomials f, if char(F) = 0 or
char(F) > d r , then trdeg(f) = rankF(x) Jx (f). This yields a randomized poly-time algorithm by Lemma 2.2.
For other fields, the Jacobian criterion fails due to inseparability and AD(F) is open.
AM protocol. The Arthur-Merlin class AM is a randomized version of the class NP [4]. Arthur-Merlin
protocols, introduced by Babai [6], can be considered as a special type of interactive proof system
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 10
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
in which the randomized poly-time verifier (Arthur) and the all-powerful prover (Merlin) have only
constantly many rounds of exchange. AM contains interesting problems like verifying that two graphs are
non-isomorphic. AM ∩ coAM is the class of decision problems for which both YES and NO answers can
be verified by an AM protocol. It can be thought of as the randomized version of NP ∩ coNP. See [31]
for a few natural algebraic problems in AM ∩ coAM. If such a problem is NP-hard (even under random
reductions) then the polynomial hierarchy collapses to the second level, i. e., PH = Σ2 .
In this article, AM protocols will only be used to distinguish whether a set S is “small” or “large.”
Formally, we refer to the Goldwasser-Sipser [22] Set Lowerbound method.
Lemma 2.1 (Goldwasser-Sipser [22]). Let m ∈ N be given in binary. Suppose S is a set whose membership
can be tested in nondeterministic polynomial time and its size is promised to be either ≤ m or ≥ 2m.
Then, the problem of deciding whether |S| ≥ 2m is in AM.
See, e. g., [4, Chapter 8] for a proof. We also use the Polynomial Identity Lemma several times. The
version we use is stated below.
Lemma 2.2 (Polynomial Identity Lemma [57, 60, 16]). Let f (x1 , . . . , xn ) be a nonzero polynomial of
total degree d over a field F. Let S be a finite subset of F. Then the total number of roots of f (x1 , . . . , xn )
in Sn is bounded by d|S|n−1 .
For a proof, see [4, Lemma A.36].
Geometry. Our proof requires some basic facts and definitions from classical algebraic geometry, which
are listed below. One can also refer to a standard text, e. g., [25, 26].
Let A := F be the algebraic closure of a field F. For d ∈ N+ , write Ad for the d-dimensional affine
space over A. It is defined to be the set Ad , equipped with the Zariski topology, defined as
Definition 2.3 (Zariski topology). A subset S of Ad is closed if it is the set of common zeros of some set
of polynomials in A[X1 , . . . , Xd ]. For a set S of polynomials, the closure S is defined as the smallest closed
set containing S. A set S is dense in Ad if S = Ad . The complement of a closed set is called an open set.
A closed set is called a hypersurface if it is definable by a single polynomial. A hypersurface is a
hyperplane if its defining polynomial is linear.
Define A× := A \ {0}. Write Pd for the d-dimensional projective space over A, defined to be the
quotient set (Ad+1 \ {(0, . . . , 0)})/ ∼ where (x0 , . . . , xd ) ∼ (y0 , . . . , yd ) iff there exists c ∈ A× such that
yi = cxi for 0 ≤ i ≤ d. We use (d + 1)-tuples (x0 , . . . , xd ) to represent points in Pd . Such a (d + 1)-tuple
is called a list of homogeneous coordinates of the point it represents.
The set Pd is again equipped with the Zariski topology.
Definition 2.4 (Zariski topology on a projective space). A subset S of Pd is closed if it is the set of
common zeros of some set of homogeneous polynomials in A[X0 , . . . , Xd ].
Definition 2.5 (Variety). Closed subsets of Ad or Pd are also called algebraic sets or zero sets. An
algebraic set is irreducible if it cannot be written as the union of finitely many proper algebraic sets. An
irreducible algebraic subset of an affine (or projective) space is also called an affine variety (projective
variety, resp.).
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 11
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
(In some references, varieties are not required to be irreducible, but in this paper we always assume
they are.) An algebraic set V can be uniquely represented as the union of finitely many varieties, and
these varieties are called the irreducible components of V .
Affine zero sets are in 1-1 correspondence with radical ideals; varieties correspond to prime ideals.
Irreducible decomposition of an affine variety mirrors the factoring of an ideal into primary ideals.
Finally, note that the affine points are in 1-1 correspondence with maximal ideals; this is a simple
reformulation of Hilbert’s Nullstellensatz.
The affine space Ad may be regarded as a subset of Pd via the map (x1 , . . . , xd ) 7→ (1, x1 , . . . , xd ).
Then the subspace topology of Ad induced from the Zariski topology of Pd is just the Zariski topology of
Ad . The set Pd \ Ad is the projective subspace of Pd defined by X0 = 0, called the hyperplane at infinity.
For an algebraic subset V of Ad ⊆ Pd , the smallest algebraic subset V 0 of Pd containing V (i. e., the
intersection of all algebraic subsets containing V ) is the projective closure of V , and we have V 0 ∩ Ad = V .
To see this, note that for P = (x1 , . . . , xd ) ∈ Ad \V , there exists a polynomial Q ∈ A[X1 , . . . , Xd ] of degree
D ∈ N not vanishing on P (but vanishing on V ). Then its homogenization Q0 ∈ A[X0 , . . . , Xd ], defined by
replacing each monomial
d d
D−deg(M)
M = ∏ Xidi by X0 ∏ Xid ,i
i=1 i=1
/ V 0.
does not vanish on (1, x1 , . . . , xd ). So, (1, x) ∈
For distinct points P = (x0 , . . . , xd ), Q = (y0 , . . . , yd ) ∈ Pd , write PQ for the projective line passing
through them, i. e., PQ consists of the points (ux0 + vy0 , . . . , uxd + vyd ), where (u, v) ∈ A2 \ {(0, 0)}.
Definition 2.6 (Dimension and degree). The dimension of a variety V is defined to be the largest integer
m such that there exists a chain of varieties 0/ ( V0 ( V1 ( · · · ( Vm = V . More generally, the dimension
of an algebraic set V , denoted by dimV , is the maximal dimension of its irreducible components. E. g.,
we have dim Ad = dim Pd = d. The dimension of the empty set is −1 by convention. One-dimensional
varieties are called curves.
The degree of a variety V in Ad (or in Pd ) is the number of intersections of V with a general3 affine
subspace (projective subspace, resp.) of dimension d − dimV . More generally, we define the degree of
an algebraic set V , denoted by deg(V ), to be the sum of the degrees of its irreducible components. The
degree of an algebraic subset of Ad coincides with the degree of its projective closure in Pd .
Suppose V ⊆ Ad is an algebraic set, defined by polynomials f1 , . . . , fk . Let (a1 , . . . , ad ) ∈ Ad . Then
the set {(x1 + a1 , . . . , xd + ad ) : (x1 , . . . , xd ) ∈ V } is called a translate of V . It is also an algebraic set,
defined by fi (X1 − a1 , . . . , Xd − ad ), i = 1, . . . , k.
Definition 2.7 (Morphism). Let V ⊆ An , W ⊆ Am be affine varieties. A morphism from V to W is a
function f : V → W that is a restriction of a polynomial map An → Am .
A morphism f : V → W is called dominant if Im( f ) = W . The preimage of a closed subset under a
morphism is closed (i. e., morphisms are continuous in the Zariski topology).
3 We do not rigorously define the word general here, but just remark that it essentially means “random” in algebraic geometry.
In fact, as long as we work over a large enough field, replacing “general” by “random” would not cause any problem.
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 12
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
For a polynomial map f : An → Am and an affine variety V ⊆ An , W := f (V ) is also an affine variety
(i. e., it is irreducible). To see this, assume to the contrary that W is the union of two proper closed subsets
W1 and W2 . By the definition of closure, f (V ) is not contained in either W1 or W2 , i. e., it intersects
both. Then f −1 (W1 ) ∩V and f −1 (W2 ) ∩V are two proper closed subsets of V , and their union is V . This
contradicts the irreducibility of V .
The graph Γ f of a morphism f is the set {(x, f (x)) : x ∈ V } ⊆ V × W ⊆ An × Am . Here V × W =
{(x, y) : x ∈ V, y ∈ W } denotes the product of V and W , which is a subvariety of the (n + m)-dimensional
affine space An × Am ∼ = An+m . Note the graph Γ f is closed in An × Am : Suppose f sends x ∈ V to
( f1 (x), . . . , fm (x)) ∈ Am , where fi ∈ A[X1 , . . . , Xn ] for i ∈ [m]. And suppose V is defined by an ideal
I ⊆ A[X1 , . . . , Xn ]. Then Γ f is defined by the ideal of A[X1 , . . . , Xn ,Y1 , . . . ,Ym ] generated by I and the
polynomials Yi − fi (X1 , . . . , Xn ), i = 1, . . . , m.
3 Algebraic dependence testing: Proof of Theorem 1.1
Given f1 , . . . , fm ∈ Fq [x1 , . . . , xn ], we want to decide if they are algebraically dependent. For this problem,
AD(Fq ), we could assume, with some preprocessing, that m = n. For, m > n means that it is a YES
instance. If m < n then we could apply a “random” linear map on the variables to reduce n to m, preserving
the YES/NO instances. Also, the transcendence degree does not change when we move to the algebraic
closure Fq . The details can be found in [47, Lemmas 2.7–2.9]. So, we assume the input instance to be
f := { f1 , . . . , fn } with nonconstant polynomials.
In the following, let D := ∏i∈[n] deg( fi ) > 0 and D0 := maxi∈[n] deg( fi ) > 0. Let d ∈ N+ and q0 = qd .
The value of d will be determined later. Let f : Fnq0 → Fnq0 be the polynomial map a 7→ ( f1 (a), . . . , fn (a)).
For b = (b1 , . . . , bn ) ∈ Fnq0 , denote by Nb the size of the preimage
n o
f −1 (b) = x ∈ Fnq0 f (x) = b .
Define A := Fq and N b := #{x ∈ An | fi (x) = bi , for all i ∈ [n]} which might be ∞. Let Q ∈
Fq [y1 , . . . , yn ] be a nonzero annihilator, of minimal degree, of f1 , . . . , fn . If it exists then deg(Q) ≤ D by
Perron’s bound.
3.1 AM protocol
First, we study the independent case.
Lemma 3.1 (Dimension-zero preimage). Suppose f is independent. Then N f (a) is finite for all but at
most (nDD0 /q0 )-fraction of a ∈ Fnq0 .
Proof. For i ∈ [n], let Gi ∈ Fq [z, y1 , . . . , yn ] be the annihilator of {xi , f1 , . . . , fn }. We have deg(Gi ) ≤ D
by Perron’s bound. Consider a ∈ Fnq0 such that G0i (z) := Gi (z, f1 (a), . . . , fn (a)) ∈ Fq [z] is a nonzero
polynomial for every i ∈ [n]. We claim that N f (a) is finite for such a.
To see this, note that for any b = (b1 , . . . , bn ) ∈ An satisfying the equations fi (b) = fi (a), i ∈ [n], we
have
0 = Gi (bi , f1 (b), . . . , fn (b)) = Gi (bi , f1 (a), . . . , fn (a)) = G0i (bi ), ∀i ∈ [n] .
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 13
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
Hence, each bi is a root of G0i . It follows that N f (a) ≤ ∏i∈[n] deg(G0i ) < ∞, as claimed.
It remains to prove that the number of a ∈ Fnq0 satisfying G0i = 0, for some index i ∈ [n], is bounded by
nDD0 q0−1 · q0n . Fix i ∈ [n]. Suppose Gi = ∑dj=0 i
Gi, j z j , where di := degz (Gi ) and Gi, j ∈ Fq [y1 , . . . , yn ], for
0 ≤ j ≤ di . The leading coefficient Gi,di is a nonzero polynomial. As f1 , . . . , fn are algebraically inde-
pendent, the polynomial Gi,di ( f1 , . . . , fn ) ∈ Fq [x1 , . . . , xn ] is also nonzero. Its degree is ≤ D0 deg(Gi,di ) ≤
D0 deg(Gi ) ≤ DD0 . By Lemma 2.2, for all but at most (DD0 /q0 )-fraction of a ∈ Fnq0 , we have
Gi,di ( f1 (a), . . . , fn (a)) 6= 0,
which implies
di
G0i (z) = Gi (z, f1 (a), . . . , fn (a)) = ∑ Gi, j ( f1 (a), . . . , fn (a))z j 6= 0 .
j=0
The claim now follows from the union bound.
We need the following affine version of Bézout’s Theorem. Its proof can be found in [55, Theo-
rem 3.1].
Theorem 3.2 (Bézout’s). Let g1 , . . . , gn ∈ A[x1 , . . . , xn ]. Then the number of common zeros of g1 , . . . , gn
in An is either infinite, or at most ∏i∈[n] deg(gi ).
Combining Lemma 3.1 with Bézout’s Theorem, we obtain
Lemma 3.3 (Small preimage). Suppose f is independent. Then N f (a) ≤ D for all but at most (nDD0 /q0 )-
fraction of a ∈ Fnq0 .
Next, we study the dependent case (with an annihilator Q).
Lemma 3.4 (Large preimage). Suppose f is dependent. Then for k > 0, we have N f (a) > k for all but at
most (kD/q0 )-fraction of a ∈ Fnq0 .
Proof. Let Im( f ) := f (Fnq0 ) be the image of the map. Note that Q vanishes on all the points in Im( f ). So,
| Im( f )| ≤ Dq0n−1 by Lemma 2.2.
Let B := {b ∈ Im( f ) : Nb ≤ k} be the “bad” images. We can estimate the bad domain points as,
#{a ∈ Fnq0 : N f (a) ≤ k} = #{a ∈ Fnq0 : f (a) ∈ B} ≤ k|B| ≤ k| Im( f )| ≤ kDq0n−1 .
which proves the lemma.
Theorem 3.5 (AM). Testing algebraic dependence of f is in AM.
Proof. Fix q0 = qd > 4nDD0 + 4kD and k := 2D. Note that d will be polynomial in the input size. For an
a ∈ Fnq0 , consider the set f −1 ( f (a)) := {x ∈ Fnq0 | f (x) = f (a)}.
By Lemma 3.3 and Lemma 3.4, when Arthur picks a randomly, with high probability, | f −1 ( f (a))| =
N f (a) is more than 2D in the dependent case while ≤ D in the independent case. Note that an upper bound
on ∏i∈[n] deg( fi ) can be deduced from the size of the input circuits for the polynomials fi ; thus, we know
D. Moreover, containment in f −1 ( f (a)) can be tested in P. Thus, by Lemma 2.1, AD(Fq ) is in AM.
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 14
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
3.2 coAM protocol
We first study the independent case.
Lemma 3.6 (Large image). Suppose f is independent. Then Nb > 0 for at least (D−1 − nD0 q0−1 )-fraction
of b ∈ Fnq0 .
Proof. Let S := {a ∈ Fnq0 : N f (a) ≤ D}. Then |S| ≥ (1 − nDD0 q0−1 ) · q0n by Lemma 3.3. As every b ∈ f (S)
has at most D preimages in S under f , we have | f (S)| ≥ |S|/D ≥ (D−1 − nD0 q0−1 ) · q0n . This proves the
lemma since Nb > 0 for all b ∈ f (S).
Next, we study the dependent case.
Lemma 3.7 (Small image). Suppose f is dependent. Then Nb = 0 for all but at most (D/q0 )-fraction of
b ∈ Fnq0 .
Proof. By definition, Nb > 0 iff b ∈ Im( f ) := f (Fnq0 ). It was shown in the proof of Lemma 3.4 that
| Im( f )| ≤ Dq0n−1 . The lemma follows.
Theorem 3.8 (coAM). Testing algebraic dependence of f is in coAM.
Proof. Fix q0 = qd > D(2D + nD0 ). Note that d will be polynomial in the input size. For b ∈ Fnq0 , consider
the set f −1 (b) := {x ∈ Fnq0 | f (x) = b} of size Nb .
Define S := Im( f ). Note that b ∈ Fnq0 satisfies Nb > 0 iff b ∈ S. Thus, by Lemma 3.6, |S| ≥
(D−1 − nD0 q0−1 )q0n > 2Dq0n−1 when f is independent, and by Lemma 3.7, |S| ≤ Dq0n−1 when f is
dependent.
Note that an upper bound on ∏i∈[n] deg( fi ) can be deduced from the size of the input circuits for
the polynomials fi ; thus, we know Dq0n−1 . Moreover, containment in S can be tested in NP. Thus, by
Lemma 2.1, AD(Fq ) is in coAM.
Proof of Theorem 1.1. The statement immediately follows from Theorem 3.5 and Theorem 3.8.
4 Approximate polynomials satisfiability: Proof of Theorem 1.3
Theorem 1.3 is proved in two parts. First, we show that APS is equivalent to AnnAtZero problem, which
means that it is NP-hard [30]. Next, we utilize the beautiful underlying geometry to devise a PSPACE
algorithm.
4.1 APS is equivalent to AnnAtZero
The proof that APS is equivalent to AnnAtZero is classical and follows from two statements in algebraic
geometry and commutative algebra, which we state as Lemma 4.1 and Theorem 4.2. The first statement
(Lemma 4.1) gives a geometric reinterpretation of AnnAtZero. This can be seen as a direct application of
the ideal-variety correspondence. The second statement (Theorem 4.2) is also classical. It was essentially
proved in [37] and was also discussed in [12, Lemma 20.28] and [23, Page 37:53].
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 15
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
Let A be the algebraic closure of F. Note that for the given polynomials f := { f1 , . . . , fm } in F[x],
there is an annihilator over F with a nonzero constant term iff there is an annihilator over A with a nonzero
constant term. This is because if Q is an annihilator over A with a nonzero constant term, w.l.o.g. 1, then
by basic linear algebra, the linear system defined by the equation Q(f) = 0, in terms of the unknown
coefficients of Q, would also have a solution in F. Thus, there is an annihilator over F with constant term
1. This proves that it suffices to solve AnnAtZero over the algebraically closed field A. This provides us
with a better geometry.
Write f : An → Am for the polynomial map sending a point
x = (x1 , . . . , xn ) ∈ An to ( f1 (x), . . . , fm (x)) ∈ Am .
For a subset S of an affine or projective space, write S for its Zariski closure in that space. We will use O
to denote the origin 0 of an affine space.
The following lemma reinterprets AnnAtZero in a geometric way.
Lemma 4.1 (classical). The constant term of every annihilator for f is zero iff O ∈ Im( f ).
Proof. Note that Q ∈ A[Y1 , . . . ,Ym ] vanishes on Im( f ) iff Q(f) vanishes on An , which holds iff Q(f) = 0,
i. e., Q is an annihilator for f. So Im( f ) = V (I), where the ideal I ⊆ A[Y1 , . . . ,Ym ] consists of the
annihilators for f. Also note that {O} = V (m), where m is the maximal ideal hY1 , . . . ,Ym i.
Let us study the condition O ∈ Im( f ). By the ideal-variety correspondence, {O} = V (m) ⊆ Im( f ) =
V (I) is equivalent to I ⊆ m, i. e., Q mod m = 0 for Q ∈ I. But Q mod m is just the constant term of the
annihilator Q. Hence, we have the equivalence.
As a special case, the above lemma proves that whenever f is algebraically independent, we have
Am = Im( f ). E. g., f1 = X1 and f 2 = X1 X2 − 1.
In general, Im( f ) is not necessarily closed in the Zariski topology.
Example 2. Let n = 2, m = 3. Consider f1 = f2 = X1 and f3 = X1 X2 − 1. The annihilators are multiples
of (Y1 −Y2 ), which means by Lemma 4.1 that O ∈ Im( f ). But there is no solution to f1 = f2 = f3 = 0,
i. e., O ∈
/ Im( f ).
Approximation. Although O ∈ Im( f ) is not equivalent to the existence of a solution x ∈ An to fi = 0,
i ∈ [m], it is equivalent to the existence of an “approximate solution” x ∈ A[ε, ε −1 ]n , which is a tuple of
Laurent polynomials in a formal variable ε. The formal statement is as follows. W.l.o.g. we assume f to
be m nonconstant polynomials.
Theorem 4.2 (classical). O ∈ Im( f ) iff there exists x = (x1 , . . . , xn ) ∈ A(ε)n such that fi (x) ∈ εA[ε], for
all i ∈ [m]. Moreover, when such x exists, it may be chosen such that
( 0 )
∆
0
xi ∈ ε −∆ A[ε] ∩ ε ∆ A[ε −1 ] = ∑ c jε j : c j ∈ A , i ∈ [n],
j=−∆
where ∆ := ∏i∈[m] deg( fi ) > 0 and ∆0 := (maxi∈[m] deg( fi )) · ∆ > 0.
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 16
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
For example, choosing x = (x1 , x2 ) := (ε, 1/ε) in Example 2, we have f1 (x) = f2 (x) = ε and f3 (x) = 0.
Thus Theorem 4.2 gives another way of seeing O ∈ Im( f ) in Example 2.
As mentioned previously, Theorem 4.2 was essentially proved in [37]. We include a proof here for
the sake of completeness.
First, we recall a tool to reduce the domain from a variety to a curve, proven in [37].
Lemma 4.3 ([37, Proposition 1]). Let V ⊆ An , W ⊆ Am be affine varieties, ϕ : V → W dominant, and
t ∈ W \ ϕ(V ). Then there exists a curve C ⊆ An such that t ∈ ϕ(C) and deg(C) ≤ deg(Γϕ ), where Γϕ
denotes the graph of ϕ embedded in An × Am .
Next, [37] essentially shows that in the case of a curve one can approximate the preimage of f by
using a single formal variable ε and working in A(ε). Here A[[ε]] denotes a formal power series in ε
with coefficients from A.
Lemma 4.4 ([37, Corollary of Proposition 3]). Let C ⊆ An be an affine curve. Let f : C → Am be a mor-
phism sending x ∈ C to ( f1 (x), . . . , fm (x)) ∈ Am , where f1 , . . . , fm ∈ A[X1 , . . . , Xn ]. Let t = (t1 , . . . ,tm ) ∈
f (C). Then there exists p1 , . . . , pn ∈ ε − deg(C) A[[ε]] such that fi (p1 , . . . , pn ) − ti ∈ εA[[ε]] , for all i ∈ [m].
Finally, we use the above two lemmas to prove the connection of APS with O ∈ Im( f ), and hence
with AnnAtZero (by Lemma 4.1).
Proof of Theorem 4.2. First assume that an x, satisfying the conditions in Theorem 4.2, exists. Pick such
an x. If f is algebraically independent then by Lemma 4.1 we have that Am = Im( f ) and we are done.
So, assume that there is a nonzero annihilator Q for f. We have Q( f1 (x), . . . , fm (x)) = 0 ∈ εA[ε]. On
the other hand, as fi (x) ∈ εA[ε], for all i ∈ [m]; we deduce that Q( f1 (x), . . . , fm (x)) mod εA[ε] is Q(0),
which is the constant term of Q. So it equals zero. By Lemma 4.1, we have O ∈ Im( f ) and again we are
done.
Conversely, assume O ∈ Im( f ) and we will prove that x exists. If O ∈ Im( f ), then we can choose
x ∈ An and we are done. So assume O ∈ Im( f ) \ Im( f ). Regard f as a dominant morphism from An to
Im( f ). Its graph Γ f is cut out in An × Am by Yi − fi (X1 , . . . , Xn ), i ∈ [m]. So deg(Γ f ) ≤ ∏m i=1 deg( f i ) = ∆
by Bézout’s Theorem.
By Lemma 4.3, there exists a curve C ⊆ An such that O ∈ f (C) and deg(C) ≤ deg(Γ f ) ≤ ∆. Pick
such a curve C. Apply Lemma 4.4 to C, f |C and O, and let p1 , . . . , pn ∈ ε − deg(C) A[[ε]] ⊆ ε −∆ A[[ε]] be as
given by the lemma. Then fi (p1 , . . . , pn ) ∈ εA[[ε]], for all i ∈ [m].
For i ∈ [n], let xi be the Laurent polynomial obtained from pi by truncating the terms of degree greater
than ∆0 . When evaluating f1 , . . . , fm , at (p1 , . . . , pn ), such truncation does not affect the coefficient of ε k
for k ≤ 0 by the choice of ∆0 . So fi (x1 , . . . , xn ) ∈ εA[ε], for all i ∈ [m].
Remark 4.5. The lower bound −∆ = − ∏m i=1 deg( f i ) for the least degree of xi in ε can be achieved up to
a factor of 1 + o(1). Consider the polynomials f1 = f2 = X1 , f3 = X1d−1 X2 − 1, and fi = Xi−2 d −X
i−1 for
−(d−1)d i−2
i = 4, . . . , m, where m = n + 1. Then we are forced to choose x1 ∈ εA[ε] and xi ∈ ε · A[ε −1 ],
n−2
for i = 2, . . . , n. So the least degree of xn in ε is at most −(d − 1)d , while −∆ = −d . n−1
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 17
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
4.2 Putting APS in PSPACE
Owing to the exponential upper bound on the precision (= degree w.r.t. ε) shown in Theorem 4.2, one
expects to solve APS in EXPSPACE only. Surprisingly, in this section, we give a PSPACE algorithm.
This we do by reducing the general AnnAtZero instance to a very special instance, that is easy to solve.
Let A be the algebraic closure of the field F. Let f1 , . . . , fm ∈ F[X1 , . . . , Xn ] be given. Denote by
k the transcendence degree of F( f1 , . . . , fm )/F. Computing k can be done in PSPACE using linear
algebra [49, 15, 9, 43]. We assume k < m − 1, since the cases k = m − 1 and k = m are again easy. In
the case k = m, the input instances are always in APS since Im( f ) = Am . And in the case k = m − 1, the
ideal of the annihilators is a principal ideal, and hence has a unique generator (up to scaling). The degree
of this generator is at most ∏m i=1 deg( f i ). Thus checking whether it has a nonzero constant term can be
solved in PSPACE by solving an exponential sized linear system of equations using [15, 9, 43].
We reduce the number of polynomials from m to k + 1 as follows: Fix a finite set S ⊆ F, and choose
ci, j ∈ S at random for i ∈ [k + 1] and j ∈ [m]. For this to work, we need a large enough S and F. For
i ∈ [k + 1], let gi := ∑mj=1 ci, j f j .
Let δ := (k + 1)(maxi∈[m] deg( fi ))k /|S|. Our algorithm is immediate once we prove the following
claim.
Theorem 4.6 (Random reduction). It holds, with probability ≥ (1 − δ ), that
(1) the transcendence degree of F(g1 , . . . , gk+1 )/F equals k, and
(2) the constant term of every annihilator for g1 , . . . , gk+1 is zero iff the constant term of every annihilator
for f1 , . . . , fm is zero.
First, we reformulate the two items of Theorem 4.6 in a geometric way, and later we will analyze the
error probability.
For d ∈ N, denote by Ad (and by Pd ) the d-dimensional affine space (projective space, resp.) over
A := F. Let f : An → Am (resp. g : An → Ak+1 ) be the polynomial map sending x to ( f1 (x), . . . , fm (x))
(resp. (g1 (x), . . . , gk+1 (x))). Let O and O0 be the origin of Am and that of Ak+1 respectively. Define the
affine varieties V := Im( f ) ⊆ Am and V 0 := Im(g) ⊆ Ak+1 . Then dimV = trdeg(f) = k.
Let π : Am → Ak+1 be the linear map sending (x1 , . . . , xm ) to (y1 , . . . , yk+1 ) where yi = ∑mj=1 ci, j x j .
Then g = π ◦ f and V 0 = π(V ).4 Now (1) of Theorem 4.6 is equivalent to dimV 0 = k, and (2) is equivalent
to O0 ∈ V 0 iff O ∈ V .
f ⊆
An V = Im( f ) Am
g π|V π
⊆
V 0 = Im(g) Ak+1
We will give sufficient conditions of (1) and (2) in terms of incidence properties. Note that O ∈ V implies
O0 ∈ V 0 , since π(O) = O0 . Now suppose O 6∈ V . Let W := π −1 (O0 ), which is a linear subspace of Am .
Then O0 6∈ π(V ) iff V ∩W = 0./ However, V ∩W = 0/ does not imply O0 6∈ V 0 , as V may “get infinitesimally
close to W ” without actually meeting W , so that O0 ∈ π(V ) = V 0 . This is shown by the following example.
4 To see V 0 ⊇ π(V ), note that π −1 (V 0 ) contains Im( f ) and is closed, and hence contains V = Im( f ).
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 18
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
Example 3. Let m = 4 and ( f1 , f2 , f3 , f4 ) = (X1 , X2 , X1 X2 − 1, X1 + X2 ). Then k := trdeg(f) = 2. Let
(g1 , g2 , g3 ) = ( f1 , f3 , f1 + f2 − f4 ) = (X1 , X1 X2 − 1, 0). Suppose Am has coordinates Y1 , . . . ,Y4 and Ak+1
has coordinates Z1 , . . . , Z3 .
Then V ⊆ Am is defined by Y1Y2 −Y3 − 1 = 0 and Y1 +Y2 −Y4 = 0, and W is defined by Y1 = 0, Y3 = 0,
and Y2 −Y4 = 0. So V ∩W = 0. / But V 0 ⊆ Ak+1 is the plane Z3 = 0, which contains the origin.
To overcome the above problem, we consider projective geometry instead of affine geometry. Suppose
Am have coordinates X1 , . . . , Xm and Pm have homogeneous coordinates X0 , . . . , Xm . Regard Am as a dense
open subset of Pm via (x1 , . . . , xm ) 7→ (1, x1 , . . . , xm ). Then H := Pm \ Am ∼
= Pm−1 is the hyperplane at
infinity, defined by X0 = 0. Denote by Vc (and Wc ) the projective closure of V (W , resp.) in Pm . Then
V = Vc ∩ Am . Let WH := Wc ∩ H, which is a projective subspace of H.
For distinct points P, Q ∈ Pm , write PQ for the projective line passing through them. The following
two lemmas provide sufficient conditions for dimV 0 = k and O0 6∈ V 0 , respectively.
/ then dimV 0 = k.
Lemma 4.7. If Vc ∩WH = 0,
Proof. Assume dimV 0 < k. Choose P ∈ π(V ). The dimension of π −1 (P) ∩V is at least dimV − dimV 0 ≥
1 [25, Theorem 11.12]. Denote by Y and Z the projective closure of π −1 (P) and that of π −1 (P) ∩ V
in Pm , respectively. Then Z ⊆ Y ∩ Vc . As dim Z = dim π −1 (P) ∩ V ≥ 1 and dim H = m − 1, we have
Z ∩ H 6= 0/ [25, Proposition 11.4].
As π is a linear map, π −1 (P) = Y ∩ Am is a translate of π −1 (O0 ) = W = Wc ∩ Am . It is well known
that two projective subspaces W1 ,W2 6⊆ H have the same intersection with H iff W1 ∩ Am and W2 ∩ Am are
translates of each other.5 So, Y ∩ H = Wc ∩ H = WH . Therefore, Vc ∩WH = Vc ∩Y ∩ H ⊇ Z ∩ H 6= 0. /
/ then O0 6∈ V 0 .
Lemma 4.8. If Vc ∩Wc = 0,
Proof. Assume to the contrary that Vc ∩Wc = 0/ but O0 ∈ V 0 . We will derive a contradiction. As WH ⊆ Wc ,
we have Vc ∩WH = 0/ and hence dimV 0 = k by Lemma 4.7.
Denote by J(Vc ,WH ) the join of Vc and WH , which is defined to be the union of the projective lines PQ,
where P ∈ Vc and Q ∈ WH . It is known that J(Vc ,WH ), as the join of two disjoint projective subvarieties,
is again a projective subvariety of Pm [25, Example 6.17].
For P ∈ V , denote by WP the unique translate of W containing P. We need the following two claims.
Claim 4.9. J(Vc ,WH ) ∩ Am =
S
P∈V WP .
Proof of Claim 4.9. Consider P ∈ Vc and Q ∈ WH . If P ∈ H, the line PQ lies in H and does not meet
Am . Now suppose P ∈ Vc \ H = V . Then PQ meets OQ at the point Q. So PQ ∩ Am is a translate of
OQ ∩ Am ⊆ Wc ∩ Am = W . It follows that PQ ∩ Am ⊆ WP . This proves J(Vc ,WH ) ∩ Am ⊆ P∈V WP .
S
Conversely, let P ∈ V . Let `P be an affine line contained in WP and passing through P (note that WP
is the union of such lines). Then `P is a translate of an affine line ` ⊆ W . As `P and ` are translates
of each other, their projective closures intersect H at the same point Q. We have Q ∈ ` ∩ H ⊆ WH . So
`P = PQ ∩ Am ⊆ J(Vc ,WH ) ∩ Am .
5 Indeed, W ∩ Am is defined by linear equations m a X + a = 0 iff W ∩ H is defined by homogeneous linear equations
i ∑ j=1 j,t j 0,t i
X0 = 0 and ∑mj=1 a j,t X j = 0. So the constant terms a0,t do not matter.
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 19
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
Claim 4.10. J(Vc ,WH ) ∩ Am = π −1 (V 0 ) .
Proof of Claim 4.10. As π is a linear map, Claim 4.9 implies J(Vc ,WH ) ∩ Am ⊆ π −1 (V 0 ). We prove the
other direction by comparing dimensions. It is known that for two disjoint projective subvarieties V1 and
V2 , dim J(V1 ,V2 ) = dimV1 + dimV2 + 1 [25, Proposition 11.37 and Exercise 11.38]. Therefore,
dim J(Vc ,WH ) = dimVc + dimWH + 1 = dimV + dimW = k + dimW .
So, dim J(Vc ,WH ) ∩ Am = k + dimW . On the other hand, we have π −1 (V 0 ) ∼
= V 0 ×W . So dim π −1 (V 0 ) =
0 m −1 0
dimV + dimW = k + dimW . Now J(Vc ,WH ) ∩ A and π (V ) are (irreducible) affine varieties of the
same dimension, and one is contained in the other. So they must be equal. This proves the claim.
So π −1 (V 0 ) = P∈V WP by Claim 4.9 and Claim 4.10. As O0 ∈ V 0 , we have W = π −1 (O0 ) ⊆ π −1 (V 0 ) =
S
P∈V WP . So WP = W for some P ∈ V , since W is a linear space. But then P ∈ V ∩WP = V ∩W ⊆ Vc ∩Wc ,
S
contradicting the assumption Vc ∩Wc = 0./
Remark 4.11. The converse of Lemma 4.8 is false, as shown by the following example.
Example 4. Consider Example 3 but choose f4 to be X1 + X2 + 1 instead of X1 + X2 . Now we have
g3 = 1, V is defined by Y1Y2 −Y3 − 1 = 0 and Y1 +Y2 −Y4 + 1 = 0, and V 0 is the plane Z3 = 1. So O0 6∈ V 0 .
On the other hand, suppose Pm has coordinates Y0 , . . . ,Y4 . Then Vc ∩ H is defined by Y0 = Y1Y2 =
Y1 +Y2 −Y4 = 0, and WH is defined by Y0 = Y1 = Y2 −Y4 = Y3 = 0. So (0, 0, 1, 0, 1) ∈ Vc ∩WH ⊆ Vc ∩Wc .
Error probability. It remains to bound the probability of failure of the conditions Vc ∩WH = 0/ and (in
the case O 6∈ V ) Vc ∩Wc = 0.
/ We need the following lemma.
Lemma 4.12 (Cut by hyperplanes). Let V ⊆ Pm be a projective variety of dimension r and degree d. Let
r0 ≥ r + 1. Choose ci, j ∈ S at random, for i ∈ [r0 ] and 0 ≤ j ≤ m. Let W ⊆ Pm be the projective subspace
cut out by the equations ∑mj=0 ci, j X j = 0, i = 1, . . . , r0 , where X0 , . . . , Xm are homogeneous coordinates of
Pm . Then V ∩W = 0/ holds with probability at least 1 − (r + 1)d/|S|.
Proof. For i ∈ [r0 ], let Hi ⊆ Pm be the hyperplane defined by ∑mj=0 ci, j X j = 0. By ignoring Hi for
i > r + 1, we may assume r0 = r + 1. Let V0 := V and Vi := Vi−1 ∩ Hi for i ∈ [r0 ]. It suffices to show that
dimVi = dimVi−1 − 1 holds with probability at least 1 − d/|S|, for each i ∈ [r0 ] (the dimension of the
empty set is −1 by convention).
Fix i ∈ [r0 ] and ci0 , j , for i0 ∈ [i − 1] and 0 ≤ j ≤ m. So Vi−1 is also fixed. Note that Vi−1 6= 0/ since
taking a hyperplane section reduces the dimension by at most one. If dimVi 6= dimVi−1 − 1, then
dimVi = dimVi−1 , and Hi contains some irreducible component of Vi−1 [25, Exercise 11.6]. Let Y be
an irreducible component of Vi−1 , and fix a point P ∈ Y . Then Y ⊆ Hi only if P ∈ Hi , which holds only
if ci,0 , . . . , ci,m satisfy a nonzero linear equation determined by P. This occurs with probability at most
1/|S| (e. g., by fixing all but one ci, j ). We also have deg(Vi−1 ) ≤ deg(V ) ≤ d, and hence the number
of irreducible components of Vi−1 is bounded by d. By the union bound, Hi contains an irreducible
component of Vi−1 with probability at most d/|S|.
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 20
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
Proof of Theorem 4.6. As mentioned above, Theorem 4.6 is equivalent to showing that, with probability
at least 1−δ : (1) dimV 0 = k, and (2) O0 ∈ V 0 iff O ∈ V . Note that Wc is cut out in Pm by the linear equations
∑mj=1 ci, j X j = 0, i = 1, . . . , k + 1. So WH is cut out in H ∼
= Pm−1 (corresponding to X0 = 0) by the linear
equations ∑mj=1 ci, j X j = 0, i = 1, . . . , k + 1. We also have deg(Vc ∩ H) ≤ deg(Vc ) ≤ (maxi∈[m] deg( fi ))k
(see, e. g., [12, Theorem 8.48]).
Assume O ∈ V . Then O0 ∈ V 0 since π(O) = O0 . Applying Lemma 4.12 to each of the irreducible
components of Vc ∩ H and WH , as subvarieties of H ∼ = Pm−1 , we see Vc ∩ WH = (Vc ∩ H) ∩ WH = 0/
holds with probability at least 1 − k deg(Vc ∩ H)/|S| ≥ 1 − δ . So by Lemma 4.7, dimV 0 = k holds with
probability at least 1 − δ .
Now assume O 6∈ V . Let πO,H : Vc → H be the projection of Vc from O to H, defined by P 7→ OP ∩ H
for P ∈ Vc . It is well defined since O 6∈ Vc . The image πO,H (Vc ) is a projective subvariety of H [25,
Theorem 3.5]. If Vc ∩ Wc contains a point P, then πO,H (Vc ) ∩ WH contains πO,H (P). Conversely, if
πO,H (Vc ) ∩ WH contains a point Q, then there exists P ∈ Vc such that Q = πO,H (P), and we have P ∈
OQ ⊆ Wc . We conclude that πO,H (Vc ) ∩WH = 0/ iff Vc ∩Wc = 0, / which implies Vc ∩WH = 0. /
Note that dim πO,H (Vc ) = dimVc = k, since
πO,H (Vc ) = J({O},Vc ) ∩ H .
We also have deg(πO,H (Vc )) ≤ deg(Vc ) [25, Example 18.16]. Applying Lemma 4.12 to πO,H (Vc ) and WH ,
as subvarieties of H ∼
= Pm−1 , we see πO,H (Vc ) ∩WH = 0/ holds with probability at least
(k + 1) deg(πO,H (Vc ))
1− ≥ 1−δ .
|S|
We have shown above that πO,H (Vc ) ∩WH = 0/ imply Vc ∩WH = 0/ and Vc ∩Wc = 0.
/ By Lemma 4.7
0 0 0
and Lemma 4.8, Vc ∩WH = 0/ and Vc ∩Wc = 0/ imply dimV = k and O 6∈ V , respectively. Therefore, it
holds with probability at least 1 − δ that dimV 0 = k and O0 6∈ V 0 .
Proof of Theorem 1.3. AnnAtZero is known to be NP-hard [30]. The NP-hardness of APS follows from
Lemma 4.1 and Theorem 4.2.
Given an instance f of APS, we can first find k = trdeg(f). Fix a set S ⊆ A to be larger than
2(k + 1)(maxi∈[m] deg( fi ))k (which can be scanned using only polynomial space). Consider the points
((ci, j | i ∈ [k + 1], j ∈ [m])) ∈ S(k+1)×m ; for each such point define g := gi := ∑mj=1 ci, j f j | i ∈ [k + 1] .
Compute the transcendence degree of g, and if it is k then solve AnnAtZero for the instance g. Output
NO iff some g failed the AnnAtZero test.
All these steps can be achieved in space polynomial in the input size, using the uniqueness of the
annihilator for g [39, Theorem 47], Perron’s degree bound [49] and linear algebra [15, 9, 43].
5 Hitting set for VP: Proof of Theorem 1.4
Suppose p is a prime. Define A := F p . We want to find hitting sets for certain polynomials in A[x1 , . . . , xn ].
Fix a p-power q ≥ Ω(sr6 ), for the given parameters s, r. Assume that p - (r + 1). Also, fix a model for
the finite field Fq [1]. We now define the notion of “infinitesimally approximating” a polynomial by a
small circuit.
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 21
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
Approximative closure of VP. [10] A family ( fn |n) of polynomials from A[x] is in the class VPA if
there are polynomials fn,i and a function t : N 7→ N such that gn has a algebraic circuit of size poly(n) and
degree poly(n), over the field A(ε), computing gn (x) = fn (x) + ε fn,1 (x) + ε 2 fn,2 (x) + · · · + ε t(n) fn,t(n) (x).
That is, gn ≡ fn mod εA[ε][x].
The smallest possible circuit size of gn is called the approximative complexity of fn , namely size( fn ).
It may happen that gn is much easier than fn in terms of traditional circuit complexity. That possibility
makes the definition interesting and opens up a long line of research.
Hitting set for VPA Given functions s = s(n) and r = r(n), a finite set H ⊆ An is called a hitting
set for degree-r polynomials of approximative complexity s, if for every such nonzero polynomial f :
∃v ∈ H, f (v) 6= 0.
Explicitness. Heintz and Schnorr [27] proved that poly(n, s)-sized hitting sets exist aplenty (for degree-r
size-s polynomials) as follows.
Lemma 5.1 ([27, Theorem 4.4]). There exists a hitting set H ⊆ Fnq of size O(s2 n2 ) (assuming q ≥ Ω(sr2 ))
that hits all nonzero degree-r n-variate polynomials in A[x] that can be infinitesimally approximated by
size-s algebraic circuits.
The ultimate goal is computing such a hitting set in time poly(n, s, log qr). Before our work, the best
result known was EXPSPACE [44, 45].
Note that for the hitting-set design problem it suffices to focus only on homogeneous polynomials.
They are known to be computable by homogeneous circuits, where each gate computes a homogeneous
polynomial [58].
Universal circuit. It can simulate any circuit of size s computing a degree-r homogeneous polynomial
in A(ε)[x1 , . . . , xn ]. We define the universal circuit Ψ(y, x) as a circuit in n essential variables x and
s0 := O(sr4 ) auxiliary variables y. The variables y are the ones that one can specialize in A(ε), to compute
a specific polynomial in A(ε)[x1 , . . . , xn ]. Every specialization gives a homogeneous degree-r size-s0
polynomial. Moreover, the set of these polynomials is closed under constant multiples [21, Theorem 2.2].
Note that by [27] there is a hitting set, with m := O(s02 n2 ) points in Fnq (∵ q ≥ Ω(s0 r2 )), for the set P
of the polynomials infinitesimally approximated by the specializations of Ψ(y, x). A universal circuit
construction can be found in [51, 58]. Using the above notation, we give a criterion to decide whether a
candidate set is a hitting set.
Theorem 5.2 (hitting-set criterion). Set H =: {v1 , . . . , vm } ⊆ Fnq is not a hitting set for the family P of
the polynomials infinitesimally approximated by the specializations of Ψ(y, x) iff there is a satisfying
0
assignment (α, β ) ∈ A(ε)s × A(ε)n such that:
(1) ∀i ∈ [n], βi r+1 − 1 ∈ εA[ε], where r is the degree of the specializations of Ψ(y, x),
(2) Ψ(α, β ) − 1 ∈ εA[ε], and
(3) ∀i ∈ [m], Ψ(α, vi ) ∈ εA[ε].
Remark 5.3. The above criterion holds for algebraically closed fields A of any characteristic. Thus, it
reduces the hitting set verification problems for the family P over these fields to APS as well.
Proof. First we show that ∃x ∈ A(ε), xr+1 − 1 ∈ εA[ε] implies x ∈ A[[ε]] ∩ A(ε) (= rational functions
defined at ε = 0).
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 22
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
Claim 5.4. ∃x ∈ A(ε), xr+1 − 1 ∈ εA[ε] implies x ∈ Zr+1 + εA[[ε]], where Zr+1 is the set of (r + 1)-th
roots of unity in A.
Proof. Recall the formal power series A[[ε]] and its group of units A[[ε]]∗ . Note that for any polynomial
!
a= ∑ ai ε i
i0 ≤i≤d
with ai0 6= 0, the inverse
!−1
a−1 = ε −i0 · ∑ ai ε i−i 0
i0 ≤i≤d
is in ε −i0 · A[[ε]]∗ . This is just a consequence of the identity (1 − ε)−1 = ∑i≥0 ε i . In other words, any
rational function a ∈ A(ε) can be written as an element in ε −i A[[ε]]∗ , for some i ≥ 0. Thus, write x as
ε −i · (b0 + b1 ε + · · · ) for i ≥ 0 and b0 ∈ A∗ . This gives
xr+1 − 1 = ε −i(r+1) (b0 + b1 ε + b2 ε 2 + · · · )r+1 − 1 .
For this to be in εA[ε], clearly i has to be 0 (otherwise, ε −i(r+1) remains uncancelled), implying that
x ∈ A[[ε]].
Moreover, we deduce that br+10 − 1 = 0. Thus, Condition (1) implies that b0 is one of the (r + 1)-th
roots of unity Zr+1 ⊆ A (recall that, since p - (r + 1), |Zr+1 | = r + 1). Thus, x ∈ Zr+1 + εA[[ε]].
0
[⇒]: Suppose H is not a hitting set for P. Then, there is a specialization α ∈ A(ε)s of the
universal circuit such that Ψ(α, x) computes a polynomial in A[ε][x] \ εA[ε][x], but still “fools” H, i. e.,
∀i ∈ [m], Ψ(α, vi ) ∈ εA[ε]. What remains to be shown is that Conditions (1) and (2) can be satisfied too.
Consider the polynomial g(x) := Ψ(α, x) ε=0 . It is a nonzero polynomial, in A[x] of degree r, that
“fools” H. By Lemma 2.2, there is a β ∈ Zr+1 n such that a := g(β ) is in A∗ . Clearly, βir+1 − 1 = 0, for
all i. Consider ψ 0 := a−1 · Ψ(α, x). Note that ψ 0 (β ) − 1 ∈ εA[ε], and ψ 0 (vi ) ∈ εA[ε] for all i. Moreover,
the normalized polynomial ψ 0 (x) can easily be obtained from the universal circuit Ψ by changing one
of the coordinates of α (e. g., the incoming wires of the root of the circuit). This means that the three
0
conditions (1) – (3) can be simultaneously satisfied by (some) (α 0 , β ) ∈ A(ε)s × Zr+1 n .
0
[⇐]: Suppose the satisfying assignment is (α, β 0 ) ∈ A(ε)s × A(ε)n . As shown in Claim 5.4,
Condition (1) implies βi0 ∈ Zr+1 + εA[[ε]] for all i ∈ [n]. Let us define βi := βi0 ε=0 , for all i ∈ [n]; they
are in Zr+1 ⊆ A. By Condition (3), ∀i ∈ [m], Ψ(α, vi ) ∈ εA[ε].
Since any rational function a ∈ A(ε) can be written as an element in ε −i A[[ε]]∗ , for some i ≥ 0, we
get that Ψ(α, x) is in ε − j A[[ε]][x], for some j ≥ 0. Expand the polynomial Ψ(α, x), w.r.t. ε, as
g− j (x)ε − j + · · · + ε −2 g−2 (x) + g−1 (x)ε −1 + g0 (x) + εg1 (x) + ε 2 g2 (x) + . . . .
Let us study Condition (2). If for each 0 ≤ ` ≤ j, polynomial g−` (x) is zero, then Ψ(α, β 0 ) ε=0 = 0
contradicting the condition. Thus, we can pick the largest 0 ≤ ` ≤ j such that the polynomial g−` (x) 6= 0.
Note that the normalized circuit ε ` · Ψ(α, x) equals g−` at ε = 0. This means that g−` ∈ P, and it is a
nonzero polynomial fooling H. Thus, H cannot be a hitting set for P and we are done.
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 23
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
Proof of Theorem 1.4. Given a prime p and parameters n, r, s in unary (w.l.o.g. p - (r + 1)), fix a field Fq
with q ≥ Ω(sr6 ). Fix the universal circuit Ψ(y, x) with n essential variables x and s0 := Ω(sr4 ) auxiliary
variables y. Fix m := Ω(s02 n2 ).
For every subset H =: {v1 , . . . , vm } ⊆ Fnq solve the APS instance described by Conditions (1) – (3) in
Theorem 5.2. These are (n + m + 1) algebraic circuits of degree poly(srn, log p) and a similar bit size.
Using the algorithm from Theorem 1.3 it can be solved in space poly(srn, log p).
The number of subsets H is at most qnm . So we can go over all of them in space poly(nm log q). If
APS fails on one of them (say H) then we know that H is a hitting set for P. Since Ψ is universal, for
homogeneous degree-r size-s polynomials in A[x], we output H as the desired hitting set.
Remark 5.5. One advantage of our method compared to the one in [21] is that in our construction, the
bit complexity of the coordinates of the points in the hitting set is O(log rs), whereas the bit complexity
of those in [21] is poly(n, s, r).
6 Conclusion
Our result that algebraic dependence testing is in AM ∩ coAM gives some hope that a randomized
polynomial-time algorithm for the problem might exist. Studying the following special case might be
helpful to get an idea for designing better algorithms.
Given quadratic polynomials f1 , . . . , fn ∈ F2 [x1 , . . . , xn ], test if they are algebraically dependent in
randomized polynomial time [47].
In addition, Ilya Volkovich [59] asked whether AD(F) ∈ SBP ∩ coSBP is true, and whether our
method can be used to prove this stronger result. Here SBP, introduced in [8], stands for “small
bounded-error probability” and is a subclass of AM.
As indicated in this paper, approximate polynomials satisfiability, or equivalently testing zero-
membership in the Zariski closure of the image, may have further applications to problems in computa-
tional algebraic geometry and algebraic complexity.
We know that HN is in AM over fields of characteristic zero, assuming GRH [32]. Can we prove that
AnnAtZero (or APS) is also in AM over fields of characteristic zero assuming GRH [30]? This would
also imply a better hitting set construction for VP.
Acknowledgements. We thank Anurag Pandey and Sumanta Ghosh for insightful discussions on the
approximate polynomials satisfiability and explicit construction of hitting set for the closure of VP. We
are also grateful to the anonymous reviewers for their careful reading of the manuscript and for their many
helpful comments. We thank the editor-in-chief Laci Babai for his meticulous suggestions regarding
grammar and style. Finally, N.S. thanks the funding support from DST (DST/SJF/MSA-01/2013-14), and
Z.G. thanks the funding support from DST and Research I Foundation of CSE, IITK.
References
[1] L EONARD M. A DLEMAN AND H ENDRIK W. L ENSTRA: Finding irreducible polynomials over
finite fields. In Proc. 18th STOC, pp. 350–355. ACM Press, 1986. [doi:10.1145/12130.12166] 9, 21
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 24
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
[2] M ANINDRA AGRAWAL , S UMANTA G HOSH , AND N ITIN S AXENA: Bootstrapping variables in
algebraic circuits. Proc. Nat. Acad. of Sciences (USA), 116(17):8107–8118, 2019. Preliminary
version in STOC’18. [doi:10.1073/pnas.1901272116] 4
[3] M ANINDRA AGRAWAL , C HANDAN S AHA , R AMPRASAD S APTHARISHI , AND N ITIN S AXENA:
Jacobian hits circuits: Hitting sets, lower bounds for depth-D occur-k formulas and depth-3 tran-
scendence degree-k circuits. SIAM J. Comput., 45(4):1533–1562, 2016. Preliminary version in
STOC’12. [doi:10.1137/130910725, arXiv:1111.0582] 4
[4] S ANJEEV A RORA AND B OAZ BARAK: Computational Complexity: A Modern Approach. Cam-
bridge Univ. Press, 2009. [doi:10.1017/CBO9780511804090] 3, 5, 10, 11
[5] 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. Preliminary version in STOC’17. [doi:10.4086/toc.2019.v015a007] 3
[6] L ÁSZLÓ BABAI: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429. ACM
Press, 1985. [doi:10.1145/22145.22192] 10
[7] M ALTE B EECKEN , J OHANNES M ITTMANN , AND N ITIN S AXENA: Algebraic independence and
blackbox identity testing. Inform. and Comput., 222:2–19, 2013. Preliminary version in ICALP’11.
[doi:10.1016/j.ic.2012.10.004, arXiv:1102.2789] 2, 4, 10
[8] E LMAR B ÖHLER , C HRISTIAN G LASSER , AND DANIEL M EISTER: Error-bounded probabilistic
computations between MA and AM. J. Comput. System Sci., 72(6):1043–1076, 2006. Preliminary
version in MFCS’03. [doi:10.1016/j.jcss.2006.05.001] 24
[9] A LLAN B ORODIN , J OACHIM VON ZUR G ATHEM , AND J OHN H OPCROFT: Fast parallel matrix
and GCD computations. Inf. Control, 52(3):241–256, 1982. Preliminary version in FOCS’82.
[doi:10.1016/S0019-9958(82)90766-5] 2, 18, 21
[10] K ARL B RINGMANN , C HRISTIAN I KENMEYER , AND J EROEN Z UIDDAM: On algebraic branching
programs of small width. J. ACM, 65(5):32:1–32:29, 2018. Preliminary version in CCC’17.
[doi:10.1145/3209663, arXiv:1702.05328] 22
[11] P ETER B ÜRGISSER: The complexity of factors of multivariate polynomials. Foundations of Compu-
tational Mathematics, 4(4):369–396, 2004. Preliminary version in FOCS’01. [doi:10.1007/s10208-
002-0059-5] 5
[12] P ETER B ÜRGISSER , M ICHAEL C LAUSEN , AND A MIN S HOKROLLAHI: Algebraic Complexity
Theory. Springer, 1997. [doi:10.1007/978-3-662-03338-8] 6, 15, 21
[13] P ETER B ÜRGISSER , A NKIT G ARG , R AFAEL O LIVEIRA , M ICHAEL WALTER , AND AVI W IGDER -
SON : Alternating minimization, scaling algorithms, and the null-cone problem from invariant
theory. In Proc. 9th Innovations in Theoretical Computer Science Conf. (ITCS’18), pp. 24:1–24:20.
Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2018.24,
arXiv:1711.08039] 7
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 25
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
[14] C HI -N ING C HOU , M RINAL K UMAR , AND N OAM S OLOMON: Closure results for polyno-
mial factorization. Theory of Computing, 15(13):1–34, 2019. Preliminary version in CCC’18.
[doi:10.4086/toc.2019.v015a013] 3
[15] L ASZLO C SANKY: Fast parallel matrix inversion algorithms. SIAM J. Comput., 5(4):618–623,
1976. [doi:10.1137/0205040] 2, 18, 21
[16] R ICHARD A. D EMILLO AND R ICHARD J. L IPTON: A probabilistic remark on algebraic program
testing. Inform. Process. Lett., 7(4):193–195, 1978. [doi:10.1016/0020-0190(78)90067-4] 3, 11
[17] H ARM D ERKSEN AND G REGOR K EMPER: Computational Invariant Theory. Springer, 2015.
[doi:10.1007/978-3-662-48422-7] 3
[18] Z EEV DVIR: Extractors for varieties. Comput. Complexity, 21(4):515–572, 2012. Preliminary
version in CCC’09. [doi:10.1007/s00037-011-0023-3] 4
[19] Z EEV DVIR , A RIEL G ABIZON , AND AVI W IGDERSON: Extractors and rank extractors for
polynomial sources. Comput. Complexity, 18(1):1–58, 2009. Preliminary version in FOCS’07.
[doi:10.1007/s00037-009-0258-4] 4
[20] R ICHARD E HRENBORG AND G IAN -C ARLO ROTA: Apolarity and canonical forms for homoge-
neous polynomials. Eur. J. Combinatorics, 14(3):157–181, 1993. [doi:10.1006/eujc.1993.1022]
2
[21] M ICHAEL A. F ORBES AND A MIR S HPILKA: A PSPACE construction of a hitting set for the
closure of small algebraic circuits. In Proc. 50th STOC, pp. 1180–1192. ACM Press, 2018.
[doi:10.1145/3188745.3188792] 4, 7, 10, 22, 24
[22] S HAFI G OLDWASSER AND M ICHAEL S IPSER: Private coins versus public coins in interactive
proof systems. In S ILVIO M ICALI, editor, Randomness in Computation, volume 5 of Advances in
Computing Research, pp. 73–90. JAI Press, 1989. Preliminary version in STOC’86. 11
[23] J OSHUA A. G ROCHOW AND T ONIANN P ITASSI: Circuit complexity, proof complexity, and
polynomial identity testing: The ideal proof system. J. ACM, 65(6):37:1–37:59, 2018. Preliminary
version in FOCS’14. [doi:10.1145/3230742] 7, 15
[24] Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU: Algebraic dependencies and
PSPACE algorithms in approximative complexity. In Proc. 33rd Computational Complexity
Conf. (CCC’18), pp. 10:1–10:21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.
[doi:10.4230/LIPIcs.CCC.2018.10, arXiv:1801.09275] 1
[25] J OE H ARRIS: Algebraic Geometry: A First Course. Springer, 1992. [doi:10.1007/978-1-4757-
2189-8] 8, 11, 19, 20, 21
[26] ROBIN H ARTSHORNE: Algebraic Geometry. Springer, 1977. [doi:10.1007/978-1-4757-3849-0] 11
[27] J OOS H EINTZ AND C LAUS -P ETER S CHNORR: Testing polynomials which are easy to compute. In
Proc. 12th STOC, pp. 262–272. ACM Press, 1980. [doi:10.1145/800141.804674] 4, 9, 22
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 26
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
[28] AUBREY W. I NGLETON: Representation of matroids. Combinatorial Mathematics and its applica-
tions, pp. 149–167, 1971. 2
[29] C ARL G USTAV JACOB JACOBI: De Determinantibus functionalibus. Journal für die reine und
angewandte Mathematik (Crelles J.), 1841(22):319–359, 1841. [doi:10.1515/crll.1841.22.319] 2,
10
[30] N EERAJ K AYAL: The complexity of the annihilating polynomial. In Proc. 24th IEEE
Conf. on Computational Complexity (CCC’09), pp. 184–193. IEEE Comp. Soc. Press, 2009.
[doi:10.1109/CCC.2009.37] 2, 3, 9, 15, 21, 24
[31] N EERAJ K AYAL AND N ITIN S AXENA: Complexity of ring morphism problems. Comput. Complex-
ity, 15(4):342–390, 2006. [doi:10.1007/s00037-007-0219-8] 11
[32] PASCAL KOIRAN: Hilbert’s Nullstellensatz is in the polynomial hierarchy. J. Complexity, 12(4):273–
286, 1996. [doi:10.1006/jcom.1996.0019] 5, 6, 9, 24
[33] J ÁNOS KOLLÁR: Sharp effective Nullstellensatz. J. Amer. Math. Soc., 1(4):963–975, 1988.
[doi:10.2307/1990996] 5
[34] M RINAL K UMAR AND S HUBHANGI S ARAF: Arithmetic circuits with locally low alge-
braic rank. Theory of Computing, 13(6):1–33, 2017. Preliminary version in CCC’16.
[doi:10.4086/toc.2017.v013a006, arXiv:1806.06097] 4
[35] J OSEPH M. L ANDSBERG: Tensors: Geometry and Applications. Amer. Math. Soc., 2012.
[doi:10.1090/gsm/128] 6
[36] F RANÇOIS L E G ALL: Powers of tensors and fast matrix multiplication. In Proc. 39th Inter-
nat. Symp. Symbolic and Algebraic Computation (ISSAC’14), pp. 296–303. ACM Press, 2014.
[doi:10.1145/2608628.2608664, arXiv:1401.7714] 6
[37] T HOMAS L EHMKUHL AND T HOMAS L ICKTEIG: On the order of approximation in approximative
triadic decompositions of tensors. Theoret. Comput. Sci., 66(1):1–14, 1989. [doi:10.1016/0304-
3975(89)90141-2] 5, 9, 15, 17
[38] 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] 28
[39] H IDEYUKI M ATSUMURA: Commutative Algebra. Benjamin-Cummings Pub Co, 1980. 3, 21
[40] E RNST W. M AYR AND A LBERT R. M EYER: The complexity of the word problems for commu-
tative semigroups and polynomial ideals. Adv. Math., 46(3):305–329, 1982. [doi:10.1016/0001-
8708(82)90048-2] 5
[41] J OHANNES M ITTMANN , N ITIN S AXENA , AND P ETER S CHEIBLECHNER: Algebraic independence
in positive characteristic: A p-adic calculus. Trans. Amer. Math. Soc., 366(7):3425–3450, 2014.
[doi:10.1090/S0002-9947-2014-06268-5, arXiv:1202.4301] 3, 4
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 27
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
[42] 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(3):6–12,
1954. [doi:10.1109/IREPGELC.1954.6499441] 3
[43] K ETAN D. M ULMULEY: A fast parallel algorithm to compute the rank of a matrix over
an arbitrary field. Combinatorica, 7(1):101–104, 1987. Preliminary version in STOC’86.
[doi:10.1007/BF02579205] 2, 18, 21
[44] K ETAN D. M ULMULEY: Geometric complexity theory V: Equivalence between blackbox deran-
domization of polynomial identity testing and derandomization of Noether’s normalization lemma.
In Proc. 53rd FOCS, pp. 629–638. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.15] 4,
7, 22
[45] K ETAN D. M ULMULEY: Geometric complexity theory V: Efficient algorithms for Noether
normalization. J. Amer. Math. Soc., 30(1):225–309, 2017. Preliminary version in FOCS’12.
[doi:10.1090/jams/864, arXiv:1209.5993] 4, 5, 6, 7, 22
[46] Ø 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 [38, Theorem 6.13]. 3
[47] A NURAG PANDEY, N ITIN S AXENA , AND A MIT S INHABABU: Algebraic independence over
positive characteristic: New criterion and applications to locally low-algebraic-rank circuits. Comput.
Complexity, 27(4):617–670, 2018. Preliminary version in MFCS’16. [doi:10.1007/s00037-018-
0167-5] 3, 4, 8, 13, 24
[48] O SKAR P ERRON: Algebra. I: Die Grundlagen. Walter de Gruyter, 1927. 2
[49] A RKADIUSZ P ŁOSKI: Algebraic dependence of polynomials after O. Perron and some applications.
In Computational Commutative and Non-Commutative Algebraic Geometry, pp. 167–173. IOS
Press, 2005. 2, 18, 21
[50] C LAUDIU R AICU: Secant varieties of Segre–Veronese varieties. Algebra & Number Theory,
6(8):1817–1868, 2012. [doi:10.2140/ant.2012.6.1817] 6
[51] 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] 22
[52] N ITIN S AXENA: Progress on polynomial identity testing. Bulletin of the EATCS, 99:49–79, 2009.
Online version ECCC TR09-101. 7
[53] N ITIN S AXENA: Progress on polynomial identity testing - II. In Perspectives in Computational
Complexity, pp. 131–146. Springer, 2014. [doi:10.1007/978-3-319-05446-9_7, arXiv:1401.0976] 7
[54] M ARCUS S CHAEFER AND DANIEL Š TEFANKOVI Č: The complexity of tensor rank. Theory of
Computing Systems, 62(5):1161–1174, 2018. [doi:10.1007/s00224-017-9800-y, arXiv:1612.04338]
6
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 28
A LGEBRAIC D EPENDENCIES AND PSPACE A LGORITHMS IN A PPROXIMATIVE C OMPLEXITY
[55] J OACHIM S CHMID: On the affine Bezout inequality. manuscripta mathematica, 88(1):225–232,
1995. [doi:10.1007/BF02567819] 14
[56] W OLFGANG M. S CHMIDT: Equations over Finite Fields: An Elementary Approach. Volume 536
of Lecture Notes in Math. Springer, 1st edition, 1976. [doi:10.1007/BFb0080437] 3
[57] JACOB T. S CHWARTZ: Fast probabilistic algorithms for verification of polynomial identities. J.
ACM, 27(4):701–717, 1980. Preliminary version in EUROSAM’79. [doi:10.1145/322217.322225]
3, 11
[58] A MIR S HPILKA AND A MIR Y EHUDAYOFF: Arithmetic circuits: A survey of recent results and
open questions. Foundations and Trends in Theoretical Computer Science, 5(3–4):207–388, Now
Publ., 2009. [doi:10.1561/0400000039] 7, 22
[59] I LYA VOLKOVICH: Private Communication, 2018. 24
[60] R ICHARD E. Z IPPEL: 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, 11
AUTHORS
Zeyu Guo
Postdoctoral researcher
University of Haifa
Haifa, Israel
zguotcs gmail com
http://zeyuguo.bitbucket.io
Nitin Saxena
Professor of CSE
Indian Institute of Technology Kanpur
Kanpur, India
nitin cse iitk ac edu
http://www.cse.iitk.ac.in/users/nitin
Amit Sinhababu
Ph. D. student
Indian Institute of Technology Kanpur
Kanpur, India
amitks cse iitk ac edu
http://www.cse.iitk.ac.in/users/amitks
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 29
Z EYU G UO , N ITIN S AXENA , AND A MIT S INHABABU
ABOUT THE AUTHORS
Z EYU G UO is a postdoctoral researcher at the University of Haifa. Previously, he was a
postdoc at the Indian Institute of Technology Kanpur. He grew up in northern China and
completed his Bachelor’s degree at Fudan University, Shanghai. He earned his Ph. D.
at Caltech in 2017, where his advisor was Chris Umans. His Ph. D. thesis studies the
problem of deterministic univariate polynomial factoring over finite fields. His research
interests include algebraic methods in theoretical computer science, pseudorandomness
and its connections with coding theory, algorithms in number theory and algebra.
N ITIN S AXENA received his Ph. D. from the Indian Institute of Technology Kanpur in
2006. His advisor was Manindra Agrawal. He also spent stints at Princeton University
(2003-04) and at the National University of Singapore (2004-05). He was a postdoc at
the Centrum voor Wiskunde en Informatica in Amsterdam (2006-08) and a faculty at the
Hausdorff Center for Mathematics in Bonn (2008-13). Nitin’s long-term interests are in
algebra-flavored computational complexity problems.
He has contributed to primality testing, polynomial identity testing, algebraic dependence
testing, polynomial factoring and polynomial equivalence problems. Some of these
works have been awarded the Gödel prize, Fulkerson prize, CCC best paper (2006), and
ICALP best paper (2011). He enjoys interacting with, and mentoring, enthusiastic young
researchers. In his spare (and non-spare) time he enjoys listening to music, watching
movies, reading non-fiction, swimming and travelling.
A MIT S INHABABU is a Ph. D. student at the Indian Institute of Technology Kanpur. His
advisor is Nitin Saxena. Currently he is visiting Ulm University, Ulm, Germany and is
affiliated with HTW Aalen, where his mentor is Thomas Thierauf. Amit grew up in West
Bengal, India. He completed his Bachelor’s degree at Bengal Engineering and Science
University Shibpur, now known as IIEST Shibpur, and his Masters at IIT Kanpur. His
current research interests are in algebraic complexity and computational complexity. He
likes reading fiction and listening to Indian classical music.
T HEORY OF C OMPUTING, Volume 15 (16), 2019, pp. 1–30 30