Beating Brute Force for Systems of Polynomial Equations over Finite Fields∗
Daniel Lokshtanov†Ramamohan Paturi‡

Suguru Tamaki§

Ryan Williams¶

Huacheng Yu¶
Abstract

1 Introduction

We consider the problem of solving systems of multivariate
polynomial equations of degree k over a finite field. For every
integer k ≥ 2 and finite field Fq where q = pd for a primep, we give, to the best of our knowledge, the first algorithms
that achieve an exponential speedup over the brute force O(qn )time algorithm in the worst case. We present two algorithms,
a randomized algorithm with running time qn+o(n) · q−n/O(k)q −dnotherwise, wheretime if q ≤ 24ekd , and qn+o(n) · ( logdek )e = 2.718 . . . is Napier’s constant, and a deterministic algorithm
6/7d
for counting solutions with running time qn+o(n) · q−n/O(kq ) .
For the important special case of quadratic equations in F2 , ourrandomized algorithm has running time O(20.8765n ).
For systems over F2 we also consider the case where the input
polynomials do not have bounded degree, but instead can be
efficiently represented as a ΣΠΣ circuit, i.e., a sum of productsof sums of variables. For this case we present a deterministic
algorithm running in time 2n−δ n for δ = 1/O(log(s/n)) for
instances with s product gates in total and n variables.
Our algorithms adapt several techniques recently developed
via the polynomial method from circuit complexity. The algorithm for systems of ΣΠΣ polynomials also introduces a newdegree reduction method that takes an instance of the problem
and outputs a subexponential-sized set of instances, in such a
way that feasibility is preserved and every polynomial among
the output instances has degree O(log(s/n)).

We consider the problem of solving systems of multivariate polynomial equations over a finite field of order q =pd . For brevity, we call the problem SysPolyEqs(q). An
instance P of the problem has the form {p1 , p2 , . . . , pm },where each pi ∈ Fq [x1 , x2 , . . . , xn ] and is represented as asum of monomials where the exponent of each variable is
at most q − 1 (due to the identity xq = x). Our task is todecide whether P is feasible, i.e., whether there exists anx ∈ Fnq such that p1 (x) = p2 (x) = · · · pm (x) = 0 holds. We
call such an x a satisfying assignment to P.
We define the degree of an instance as
max1≤i≤m deg(pi ), where deg(pi ) is the maximum
degree of the monomials of pi and the degree of amonomial is defined as the sum of the exponents of thevariables in it. For instances of degree one, the problem
is solvable in polynomial time by Gaussian elimination.
An easy reduction from the circuit satisfiability problem
shows that SysPolyEqs(2) is NP-complete for degree-2
instances. In addition, Håstad [18] showed that, givena degree-k instance, it is NP-hard to find an assignment
to a feasible SysPolyEqs(2) instance that satisfies a(21−k − 21−2k + ε )-fraction of equations for any k ≥ 2and ε > 0. Thus the problem is extremely hard to
approximate.
In terms of exact solvability, there are few positive results known. Although several algorithms for
SysPolyEqs(2) are known in the crypto community basedon plausible average-case assumptions (see the section
on related work), to the best of our knowledge no algorithm running in qδ n time (for some fixed δ < 1) has beenreported for the general case of SysPolyEqs(q), for any
prime power q and any degree larger than 1.

∗ This work was done in part while the authors were visiting theSimons Institute for the Theory of Computing, Berkeley, CA.
† University of Bergen daniello@ii.uib.no. Supported by
the Beating Hardness by Pre-processing grant of theBergen Research Foundation‡ University of California, San Diego paturi@cs.ucsd.edu. This
research is supported by NSF grant CCF-1213151 from the Divisionof Computing and Communication Foundations. Any opinions, findings
and conclusions or recommendations expressed in this material are thoseof the authors and do not necessarily reflect the views of the National
Science Foundation.
§ Kyoto University tamak@kuis.kyoto-u.ac.jp. Supported inpart by MEXT KAKENHI (24106003); JSPS KAKENHI (25240002,
26330011); the John Mung Advanced Program of Kyoto University. Partof the work performed while the author was at Department of Computer
Science and Engineering, University of California, San Diego.
¶ Stanford
University.
rrw@cs.stanford.edu,
yuhch123@gmail.com. Supported by an Alfred P. Sloan Fellowship and NSF grants CCF-1212372 and CCF-1552651 (CAREER). Any
opinions, findings, and conclusions or recommendations expressed inthis material are those of the author(s) and do not necessarily reflect theviews of the NSF.

1.1 Our Results We present algorithms for the problem
that beat brute force search decisively for bounded degree
instances in all finite fields.
T HEOREM 1.1. (Solving Low-Degree Systems of Polynomial Equations). Let p be a prime, and q = pd for d ≥ 1.
There is a randomized algorithm that, given an instanceof SysPolyEqs(q) with m polynomial equations of degree
at most k in n variables, decides the satisfiability of thesystem correctly with high probability. The running time

of the algorithm is bounded byof variables. Again we obtain one deterministic and one
randomized algorithm, with the deterministic algorithm• O⋆ (20.8765n ) time1 when q = k = 2,
counting the number of satisfying assignments. However,
1 n
1−• O⋆ (q( 5k ) · n3k ) when p = 2 (but q > 2 or k > 2), in this case the difference between the running times ofthe deterministic and the randomized algorithms is only
• O⋆ (q(1−(1/200k))n · n3kq ) when p > 2 and log p < 4ek, in the constant factor in the savings.
( ()−dn )
log q⋆nwhen p > 2 and log p ≥ 4ek,
• O q · ekd
T HEOREM 1.3. (Solving Systems of ΣΠΣ Polynomials).
There is a randomized algorithm that, given an instanceof GenSysPolyEqs(2) of size u withs products) and n
where e = 2.718 . . . is Napier’s constant.
(
1−

1

n

10 log(s/n)+O(1)variables, runs in time poly(u) · 2, and
The running time bounds of Theorem 1.1 can be interdecides the satisfiability of the system correctly with highpreted in the following way. When the base of the field
probability.
size is “small” relative to the degree, that is, p < 24ek , thealgorithm outperforms brute force by a multiplicative fac- T HEOREM 1.4. (Counting Solutions to Systems of ΣΠΣ
tor of qn/O(k) . This corresponds to not having to guess on Polynomials). There is a deterministic algorithm that,a 1/O(k) fraction of the variables, and is qualitatively the given an instance of GenSysPolyEqs(2) of size u withsame kind of “savings” as that of the fastest known algo- s products and n variables, runs in time poly(u) ·()
1rithms for k-SAT [32]. It would be quite surprising to see
1− 1100 log(s/n)+O(1)nand counts the number of satisfying
an algorithm for SysPolyEqs(q) beating brute force by a 2
assignmentsforthesystem.
n/O(k)
factor more than q. When the base p of the field size
becomes “very large” compared to the degree bound, i.e.,
Note that if the degree of each ΣΠΣ polynomial islog p ≥ 4ek, the algorithm no longer achieves the multi- at most k, then one can in principle use the algorithms
plicative factor qn/O(k) improvement over brute force, in- of Theorems 1.1 and 1.2 to solve GenSysPolyEqs(2).
()dnqstead the improvement is a factor log, which is still However, in general the degree of each ΣΠΣ circuit inekd
our instances can be larger than n, and our algorithm
substantial and for example much larger than qO(n/kq) .
for GenSysPolyEqs(2) can still run in time that is superThe algorithm of Theorem 1.1 is randomized, a naturalpolynomially faster than 2n .
goal is to obtain a deterministic algorithm with the samerunning time. We are currently unable to achieve this goal,
1.2 Related Work Solving systems of multivariate
but we do obtain a deterministic algorithm that decisively
polynomial equations is a fundamental problem in mathebeats brute force and also solves the problem of counting
matics, science and engineering; see for example [11, 36].
the number of satisfying assignments.
The problem of detecting rational points in Fq (finding a
non-zero point that makes a polynomial zero) is widely
T HEOREM 1.2. (Counting Solutions to Low-Degree Sysstudied ([8, 19, 25, 26]).
tems of Polynomial Equations). Let q = pd for a prime
p and integer d ≥ 1. There is a deterministic algorithm Systems of Degree-Two. For fields of characteristic twothat, given an instance of SysPolyEqs(q) with m polyno- and the polynomials of degree two, the problem arises
mial equationsof degree
at most k in n variables, runs in in breaking certain cryptosystems based on the presumed()
hardness of quadratic polynomial equations [4, 16]. This
1
n 1−
+o(n)
300kq6/7dtime q· mO(kq) and counts the number underscores the importance of beating exhaustive searchof satisfying assignments for the system.
in the degree-2 case. For the purposes of this paragraph,
we call the problem Deg2-SysPolyEqs(q). Woods [41]We then proceed to consider the case of polynomial gave an interesting nondeterministic proof system forequations in Fq where the input polynomials do not have Deg2-SysPolyEqs(q), showing how one can prove thatbounded degree, but instead can be encoded efficiently as a system of quadratic equations is infeasible with ana ΣΠΣ circuit; i.e., a linear form of products of linear O⋆ (qn/2 )-length proof verifiable in O⋆ (qn/2 ) time. Under
forms on the variables. Specifically, we require that an several algebraic assumptions, Yang and Chen [42] estiencoding of each pi as a ΣΠΣ circuit is provided as input. mate an O(20.875n ) time bound for Deg2-SysPolyEqs(2).
We call this variant of the problem GenSysPolyEqs(q). Miura et al. [30] show how to solve Deg2-SysPolyEqs(2)For q = 2 we obtain an algorithm that achieves exponen- in polynomial time when the system is sufficiently undertial speedup over 2n as long as the total number of product determined (in particular, the number of variables n ≥gates in the input polynomials is linear in the number n Ω(m2 ), where m is the number of equations). Bardet
et al. [5] gave algorithms for Deg2-SysPolyEqs(2) run1 The O⋆ notation omits polynomial factors.
ning in deterministic 20.841n time and Las Vegas 20.792n

time for the case m = n under certain algebraic assumptions on the instances. In general, considerable researchin modern cryptanalysis is centered around solving multivariate systems of low-degree polynomial equations (seethe books [17, 3]).

1.3 Techniques Given a set of degree-k polynomials
S = {p1 , . . . , pm } ⊆ Fq [x1 , . . . , xn ], we can define a single
polynomial capturing all of them, namely PS (x) := 1 −q−1 ). For all a ∈ Fn , note that P (a) = 0∏mSqi=1 (1 − pi (x)holds if p1 (a) = · · · = pm (a) = 0, and PS (a) = 1 otherwise.
For some appropriately chosen n′ < n, we may define
Efficient Algorithms For Special Cases. Lu [28] gave a a polynomial R ∈ F [x , . . . , x ′ ] as R(x , . . . , x ′ ) :=
q 1
1
n−n
n−n
deterministic algorithm for finding a solution to a single∏a∈Fnq′ PS (x1 , . . . , xn−n′ , a). Observe that there is an a ∈ Fnq
polynomial equation that runs in time poly(s) for polynon−n′mials with s monomials. Building on a randomized al- such that PS (a) = 0 if and only if there is a b ∈ Fq
gorithm of Huang and Wong [19], Kayal [22] gave a de- such that′ R(b) = 0. Therefore, evaluating R on all points
terministic algorithm for SysPolyEqs(q) that has running a ∈ Fqn−n will determine if the original system is feasible
O(n)time d n · poly(m, log q), where n is the number of vari- or not. Evaluation of R(a) would be relatively easy if it
ables, d is the degree, and m is the number of equations. were merely a sum of products, but it is more complex:of monomials.
This algorithm is only non-trivial when q is extremely a product of sums of products of sums
n′ functions, it takesO(n)However,
since
R(y)
is
a
product
of
q
n
n
≪q .
large relative to the degree, in particular d′time qn · poly(n) to evaluate R(y) at a single point y.
Conditional Lower Bounds Based on SysPolyEqs(2). Hence the straightforward way of evaluating R on qn−n′
In some papers, the conjecture that SysPolyEqs(2) in points would lead to a qn · poly(n) running time.
degree-2 cannot be solved in 2n(1−ε ) time for any ε > 0
Despite the complexity of R, we can in fact evaluate on
was used to justify the optimality of certain algorithms. qn−n′ points in qn−n′ · poly(n, m) time by deftly applying
Björklund et al. [10] showed that the conjecture implies the probabilistic polynomial constructions of Razborov
that their algorithm for listing triangles in sparse graphs and Smolensky together with an algorithm for efficientis optimal. Vassilevska and Williams [37] prove that the sums-of-monomials evaluation. These are among the couconjecture implies that finding a zero-edge-sum triangle ple of ideas required to prove Theorem 1.1; attaining aover F2 requires n3−o(1) time; this problem is closely deterministic algorithm requires substantially more work.
related to the 3XOR problem of Jafargholi and Viola [21]. We borrow some tools from recent work of Chan and
Clearly, Theorem 1.1 refutes the above conjecture, and Williams [13], who give a more efficient deterministic alopens up the possibility for faster algorithms for the above gorithm for counting SAT assignments. Generalizing the
problems.
ideas of their #SAT algorithm to fit the SysPolyEqs(q)Relationshipto
SAT.
SysPolyEqs(2)and setting requires some care, in particular, the restriction
GenSysPolyEqs(2) may be seen as generalizations to prime fields. To make a deterministic algorithm thatof the satisfiability problem for CNF formulas: The works for all fields we give a reduction that transforms aformer is equivalent to SAT of unbounded-fan-in system of m polynomial equations of degree k with n variAND-PARITY-AND circuits, and the latter is SAT of ables over F pd for d ≥ 2 into an equivalent system of md
unbounded-fan-in AND-PARITY-AND-PARITY cir- polynomial equations of degree k with nk variables overcuits. Small-depth unbounded-fan-in circuits with AND, F p . This reduction turns out to be also useful to obtain
OR and PARITY gates (i.e., AC0 [⊕]) are widely studied an additional speedup for the randomized algorithm in thedin Boolean circuit complexity; see, e.g., [24, 15, 14]. To case that q = p .
nthe best of our knowledge, faster-than-2 SAT algorithms
Our algorithms for solving systems of ΣΠΣ polywere not known even for depth-3 unbounded-fan-in nomials (Theorems 1.3 and 1.4) consist of two steps.
circuits with a linear number of AND and PARITY gates. First, given an instance, we run a degree reduction algoWilliams [39] gave an algorithm for the ACC0 -SAT rithm that produces a set of instances of degree at mostproblem, which includes SysPolyEqs(2) as a special O(log(s/n)) such that the original instance is satisfiable ifcase; however, the algorithm of Williams only runs in and only if at least one of them is satisfiable. Then, weεpoly(n, m) · 2n−n time, where ε is a small positive con- apply the algorithms of Theorems 1.1 or 1.2 to each instant. Chapter 4.3 of Matthews’ PhD thesis [29] cites Lok- stance. Our degree reduction algorithm can be seen as ashtanov and Paturi (two authors of the present paper) with generalization of Schuler’s width reduction algorithm foran unpublished algebraic algorithm for k-SAT. Our algo- CNF-SAT [34].
The degree reduction algorithm implies that an ANDrithms for systems of degree-k equations can be seen asa considerable extensions of their method. Williams and PARITY-AND-PARITY circuit can be represented as a
Lokshtanov-Paturi were based on the polynomial method “small-size” algebraic decision tree whose internal nodes
in Boolean circuit complexity [6] (see the survey [40] for and leaves correspond to indicator functions of affinemore).
subspaces and low-degree polynomials respectively. Suchrepresentation might be useful in proving average-caselower bounds for AND-PARITY-AND-PARITY circuits,as Impagliazzo, Matthews and Paturi [20] used Schuler’s
width reduction algorithm to obtain correlation bounds
for AC0 circuits (i.e., bounded-depth unbounded-fan-in
circuits with AND and OR gates) for approximating the
PARITY function.

q−1→ Fq . This gives∑i=0 Pi (x2 , . . . , xn )x1i for some Pi : Fn−1q
us a way to decompose the problem into q subproblems.
The running time T (n) of the algorithm satisfies T (n) =qT (n − 1) + poly(n)qn and we have T (n) = poly(n) · qn .

L EMMA 2.3. (Fast Evaluation of Integer Polynomials).
Let n-variate integer polynomial P have at most pn/7
monomials such that the maximum absolute value of P(x)over all x ∈ {0, 1, . . . , p − 1}n is at most M. Then we
2 Preliminaries
can evaluate P(x) over all points in {0, 1, ..., p − 1}n in
We use random access machines as our computation poly(log M) · pn+o(n) time.
model. For a positive integer n, [n] denotes the set{1, 2, . . . , n}. For rational numbers a < b, (a, b) denotes Lemma 2.3 does not follow from the usual techniques,
the open interval between a and b. For a finite set S, such as dynamic programming [9] or divide and con|S| denotes the cardinality of S. We use the following quer [38], because P could have arbitrary degree. Below
notation: Z denotes the set of integers, Z≥0 denotes the we give a proof sketch.
set of non-negative integers, Zm denotes the quotient ringn/7 be the number of monomials. Letof integers modulo m, identified with {0, 1, . . . , m−1} and Proof. Let t ≤ pn/2
Fq denotes the finite field of order q. We use 0 and 1 to a1 . . . , a pn/2 ∈ {0, ..., p − 1} be a list of all assignmentsγγ
denote the additive identity and the multiplicative identity to n/2 variables. Let m1 = c1 x 1 , . . . , mt = ct x t be a listof monomials in P. Prepare matrices A and B of pn/2
of Fq .
n/7 and pn/7 by pn/2 dimensions, respectively, withLet x1 , x2 , . . . , xn be formal variables. A monomial is by p⃗
a product of powers of variables and a constant. For the following definitions: A[i, j] = m j (ai , 1) and B[ j, k] =γγ ∈ Zn≥0 , we define xγ := ∏i∈[n] xi i . We can represent m j (⃗1, ak )/c j , where ⃗1 denotes the all-ones assignment on
a polynomial P(x) as a sum of monomials of the form n/2 variables.
Observe that A[i, j]B[ j, k] = m j (ai , ak ). It follows that∑γ aγ xγ where aγ is the coefficient of xγ . In this paper, we(AB)[i, k] = ∑ j m j (ai , ak ) = P(ai , ak ). Thus, a matrix
consider polynomials over Fq and over Z.
When dealing with polynomials over Fq , we will only multiplication of A and B yields the value of P on all
be concerned with them for the purpose of eventually points.
Le Gall [27] gives a matrix multiplication algorithm
evaluating them over Fq . The identity xiq = xi then implies
that every monomial can be represented as xγ for γ ∈ Znq , which can multiply N by N 0.3 and N 0.3 by N matrices
without changing what the monomial evaluates to when in N 2+o(1) arithmetic operations, over any finite field.
We can therefore multiply A and B over any field Fq in
the variables takes values from Fq .
The degree of a monomial xγ is ∑i γi . Thus, the O(pn+o(n) ) arithmetic operations. Select q to be a prime
degree of a monomial is the sum of the exponents of the greater than 2M + 1. Our matrix multiplication now takes
variables in the monomial. We define M(n, k, q) to be the poly(log M)pn+o(n) time.
number of different monomials of degree at most k on n
Now for all (i, j) = (1, 1), . . . , (pn/2 , pn/2 ), consider
variables in Fq , and M(n, k) to be the number of different (AB)[i, j], and cast it as an integer r ∈ {0, 1, . . . , q}. If
monomials of degree at most k on n variables over any r ∈ {0, 1, . . . , M} then output r as the value of P(ai , a j ).
(fixed, possibly infinite) field. The degree of a polynomial Otherwise, r must be in {q − M, . . . , q − 1}; output r − q
P is the maximum degree of a monomial of P. We use the as the value of P(ai , a j ).
following facts in Section 3.
3 Randomized Algorithms for Systems of
L EMMA 2.1. The number of monomials of degree at
Polynomial Equations
most k can( be )upper bounded as follows: M(n, k, q) ≤In this section we give a proof of Theorem 1.1. A
M(n, k) ≤ n+k≤ (1 + nk )k (1 + nk )n ≤ en (1 + nk )n .
ndegree k instance of SysPolyEqs(q) is {p1 , p2 , . . . , pm },L EMMA 2.2. (Fast Evaluation in Finite Fields). There is where each pi is an Fq polynomial in formals variablesγi, ji
an algorithm that, given an Fq polynomial P in n variables x1 , x2 , . . . , xn and represented as pi (x) = ai + ∑ j=1 bi, j xnrepresented as a sum of monomials, runs in poly(n) · qn for ai , bi, j ∈ Fq , si ≥ 0 and γi, j ∈ Zq with ∑l (γi, j )l ≤ k.
time and prints a qn -dimensional vector V such that for Before proceeding with our algorithm for SysPolyEqs(q),we describe the approximation of polynomials by lowall x ∈ Fnq , V [x] = P(x) holds.
degree probabilistic polynomials due to Razborov andProof. This is a generalization of the algorithm from Smolensky [33, 35]. We begin with the following lemma
Section 6.2 in [38]. Note that we can write P as P(x) = whose proof is elementary:

L EMMA 3.1. Let Fq be a finite field andv = (v1 , v2 , . . . , vn ) ∈ Fnq \ {(0, 0, . . . , 0)}.
Selectr = (r1 , r2 , . . . , rn ) from Fnq uniformly at random.
Then, ∑i∈[n] ri vi is distributed uniformly at random overFq .

Note that if we write R(y) as a polynomial in the straightforward manner, e.g., R(y) = 1 − ∏a∈Fn′ (1 − Q(y, a)), andq
represent it as a sum of monomials, it might take time′
more than qn time. This is because R(y) has degree qn
as a polynomial in formal variables {Q(y, a)}a∈Fn′ . To req

duce the degree of R(y), we use Lemmas 3.2 and 3.1. We′n′if x = (0, 0, . . . , 0) and P(x) = 0 otherwise, i.e., P(x) = start by setting l = n + 2, for each a ∈ Fq selecting uniq−1
at random l random vectors sa,1 , sa,1 , . . . , sa,l from. . . , sl ∈ Fnq , define a poly- formly∏i∈[n] (1 − xi ). For s1 , s2 , {
} Fm
,
and
defining
)
(
q
q−1
.
nomial Pe{si }l (x) := ∏li=1 1 − ∑ j∈[n] (si ) j · x ji=1
()q−1 
Razborov and Smolensky showed that if we select randoml eelements s1 , s2 , . . . , sl ∈ Fnq uniformly and independently, Q
(y,
a)
:=
1
−
(s
)
·
p
(y,
a)
.
l
a,i
j
j
∑
∏
{sa,i }i=1

i=1
j∈[m]
then Pe{si }l (x) approximates P(x) with high probability.
Let P : Fnq → F be the function such that P(x) = 1

i=1′

L EMMA 3.2. ([33, 35]) Select random s1 , s2 , . . . , sl ∈ Fnq Next, select uniformly at random a qn -dimensional vector
uniformly and independently. Then, for all x ∈ Fnq , s over Fq and define
Pe{si }l (x) ∈ {0, 1}. Furthermore, (i) If x = (0, 0, . . . , 0),ei=1Res,{sa,i } (y) := ∑ sa · Q{sa,i }li=1 (y, a).
then Pe l (x) = 1 and (ii) if x ̸= (0, 0, . . . , 0), then′n{si }i=1

Pr{si }l [Pe{si }l (x) = 0] = 1 − q−l .
i=1

a∈Fq

i=1

′

′

By Lemma 3.2, for all y ∈ Fn−nand a ∈ Fnq , weqWe are now ready to give a randomized algorithm forehave that Q(y, a) = 1 implies Q{sa,i }li=1 (y, a) = 1, while
SysPolyEqs(q) beating brute force. We remark that the−leconstants in the exponent of Lemma 3.3 are not optimized Q(y, a) = 0 yields Pr{sa,i }li=1 [Q{sa,i }li=1 (y, a) = 0] = 1 − q .
′(with the exception for the case that q = k = 2), but chosen By Lemma 3.1, for all y ∈ Fn−n and {sa,i }, we have that,q′so as to simplify presentation.
ee(i) for all a ∈ Fnq , if Q
{sa,i }l (y, a) = 0 then Rs,{sa,i } (y) =
i=1

′

n
L EMMA 3.3. There is a randomized algorithm that, 0, and “conversely”, (ii) if there exists an a ∈ Fq such1eegiven an instance of SysPolyEqs(q) with m polynomial that Q{sa,i }li=1 (y, a) = 1, then Prs [Rs,{sa,i } (y) ̸= 0] = 1 − q .
′equations of degree at most k in n variables, decides theThus, for all y ∈ Fn−n
, we haveqsatisfiability of the system correctly with high probability. The running time of the algorithm is bounded by
1 1
1R(y) ̸= 0 ⇒Pr [Res,{sa,i } (y) ̸= 0] ≥ 1 − ≥ ,(i) O⋆ (20.8765n ) when q = k = 2, (ii) O⋆ (2(1− 5k )n · n3k )q 2s,{sa,i }3kq ) when
when q = 2 and k > 2, (iii) O⋆ (q(1−(1/(200k)))n
·
n
( (
′
1
)−n )
R(y) = 0 ⇒Pr [Res,{sa,i } (y) ̸= 0] ≤ qn · q−l ≤ ,q
3 ≤ q and log q < 4ek, and (iv) O⋆ qn · log
when
4
s,{s
}
a,i
ek

log q ≥ 4ek.

where we use the union bound for the second implication.
The algorithm repeats the following procedure t =Proof. Let P : Fnq → Fq be the function such that P(x) = 1
100n log q times: It draws the random vectors {sa,i } andif p1 (x) = p2 (x) = · · · = pm (x) = 0 and P(x) = 0 othe
erwise. We select an integer n′ = ⌊δ · n⌋ where the s, and computes a representation of Rs,{sa,i } as a sum ofexact value of δ will be set at the end of the proof monomials. The procedure then evaluates Res,{sa,i } (y) for′
to be strictly between 0 and 1 depending on k and all y ∈ Fn−nusing the algorithm of Lemma 2.2. Forqq. For formal variables y = (y1 , y2 , . . . , yn−n′ ) and con- each y ∈ Fn−n′ , the algorithm keeps a counter that keeps′qstants a = (a1 , a2 , . . . , an′ ) ∈ Fnq , we define Q(y, a) := track of the number of times the above procedure resulted′
P(y1 , y2 , . . . , yn−n′ , a1 , a2 , . . . , an′ ). Let R : Fn−n
→ Fq be in Res,{sa,i } (y) ̸= 0. The algorithm returns that the inputq
the function such that R(y) = 0 if Q(y, a) = 0 for every instance is satisfiable if there exists a y for which the′a ∈ Fnq and R(y) = 1 otherwise. P(x) is identically 0 if counter is at least 40 percent of the number of runs, that
is, at least 0.4t.
and only if R(y) is identically 0.
For the success probability analysis, suppose that the
We would like to check whether there exists an assignment to the variables such that R(y) = 1. For this purpose, input instance is satisfiable. Then there exists a y such
we represent R(y) as a sum of monomials and apply the that R(y) ̸= 0. Thus, in each of the runs of the procedure
fast evaluation algorithm for polynomials (Lemma 2.2). Res,{sa,i } (y) ̸= 0 with probability at least 1/2. Since each of

the runs of the procedure are independent, the probability This implies that a degree-2 instance of SysPolyEqs(2)that the counter for y will be at most 0.4t is at most can be solved in time O⋆ (20.8765n ).
( )()t 100n log q()t · .4tt 2−t ≤ t · 1.961≤ q2n .
2
For q = 2 we have that M(n, k, 2) ≤ nk , thus M((1 −( δ n)
Suppose now that the input instance is not satisfiable.
δ )n, k(q − 1)δ n, q) ≤ n−
= 1/(5k))wekδ n . Setting δ (Then R(y) = 0 for all choices of y and hence, in each⋆(1− 2 )n ≤run of the procedure the probability that Res,{sa,i } (y) ̸= obtain M((1 − δ )n, k(q − 1)δ n, q) ≤ O 2 10)(
0 is at most 14 . For any fixed y, the probability that O⋆ 2(1−2δ )n . Thus, for q = 2 we obtain an algorithm
the counter of y reaches above 0.4t is therefore at most1
( 1.961 )t( t ) ( 1 ).4t ( 3 ).6t
with running time O⋆ (2(1− 5k )n · n3k ).
100n log qt · .4t 4≤ t · 2.06 ≤ q2n . The union
4′
When q ≥ 3 and log q < 4ek, we set(δ =bound taken over all qn−n ≤ qn choices of y yields that the( 1/(200k),) )∗ en q + q n ,100n log q
δ
)n,
k(q
−
1)
δ
n,
q)
≤
O
then
M((1
−
probability of false positives is upper bounded by qn .
3
200
)
)
(
(
q n
≤
log q < 4ek we obtain O∗ en 3q + 200
Hence the algorithm outputs the correct answer with high using)()(
log q·0.12n
−
∗
n
∗
(1−2
δ
)n
probability.
4ek
O q ·2≤O q. Hence, in this caseWe now proceed with the running time analysis. The⋆(1−(1/200k))n
we obtain an upper bound of O (q· n3kq ) on
running time is upper bounded by t times the time taken
the running time.
to execute the main procedure once, we now upper bound′q(1/ek)this. By Lemma 2.2 it takes O⋆ (qn−n ) time to evaluate
When log q ≥ 4ek, we set δ = log log, which yields
4 log qeeRs,{sa,i } for all y once a representation of Rs,{sa,i } as a sum
M((1− δ )n, k(q−1)δ n, q) ≤ O∗ ((2ekqδ )n ). Inserting theof monomials is given.
M((1 − δ )n, k(q − 1)δ n, q) ≤definitionof δ we )obtain((n)
To upper bound the time taken to compute the represenlog log q(1/ek)∗
q · 2·log q(1/ek). Now, q1/ek ≥ 16 implies thattation of Res,{sa,i } as a sum of monomials it is sufficient to O
2·log q(1/ek)
observe that Res,{sa,i } is a polynomial in n − n′ variables of ( 2·log q(1/ek) ) log log q(1/ek)≥ q1/ek . Thus we have
log log q(1/ek)
total degree at most k(q − 1)l. We compute the represen(()n )tation of Res,{sa,i } using the definitions directly, applying
log log q(1/ek)
the naı̈ve algorithm for polynomial multiplication. How∗Oq·
2 · log q(1/ek)
ever, we make sure that whenever we are multiplying two(()n )polynomials, at least one of them has degree at most kq.
()
1 · log log q(1/ek)
1− ek(1/ek)∗
Note that this is achievable, because the only multiplica2·logq≤ Oq≤ O∗ q(1−2δ )n .
tions in the definition of Res,{sa,i } occur in the definitioneof Q{sa,i }li=1 (y, a), which is a product of polynomials of Hence, in this case we get an upper bound of
( (
)−n )
degree at most kq. Thus, the total number of operations
log q
⋆
n
on the running time.
(polynomial additions or multiplications) needed to com- O q · ek′
pute Res,{sa,i } is at most O⋆ (qn ), and each such operation
Next we show that any system of m polynomial equatakes time O⋆ (M(n − n′ , k(q − 1)(n′ + 2), q) · nkq ). Using
the observation that M(n, r + 1, q) ≤ n · M(n, r, q) for ev- tions of degree k with n variables over F pd for d ≥ 2 canery n and r we conclude that the total time taken by the be reduced in polynomial time to an equivalent system of
md polynomial equations of degree k with nk variables
algorithm is upper bounded byover F p . This allows us to substantially improve over the′′running time of the algorithm of Lemma 3.3 for the caseO⋆ (qn−n + qn · M(n − n′ , k(q − 1)n′ , q) · n3kq )when q is large compared to d, and q is a prime power pd ,⋆ (1−δ )n3kq
δn= O (q+ q · M((1 − δ )n, k(q − 1)δ n, q) · n ).
d ≥ 2.
Let p be prime. In the following, we will assume we
We now discuss the choice of δ for different possible
possess
an irreducible polynomial P(X) of degree k invalues of q and k. By always picking δ such that
⋆
(1−2
δ
)n
F
[X].
A
standard way of efficiently constructing suchpM((1− δ )n, k(q−1)δ n, q) = O (q), we ensure that
δ
)n
3kq
⋆
(1−
P(X)
is
to
choosedegree-k polynomials P at random, thenthe running time is upper bounded by O (q· n ).
test
them
for
irreducibility.
The irreducibility of P can
We divide the analysis into three cases, first the case thatthenbecheckedbyrunning
Kedlaya-Umans’
determinisq = 2, then when q ≥ 3 but q is still “small enough”
1+o(1) log2+o(1) p time ([23], Sectic
irreducibility
test
in
k
compared to d, and finally when q is “large” comparedtion 8.2); a standard algebraic fact is that a random polyto d.
nomial over F p of degree k is irreducible with probability
For q = 2 and k = 2, we set δ = 0.1235 to sat- at least 1/k. We are now ready to give the aforementioned(′)
isfy M((1 − δ )n, k(q − 1)δ n, q) ≤ n−δδnn ≤ O⋆ (2(1−2δ )n ). reduction.

L EMMA 3.4. There is a polynomial-time algorithm that D EFINITION 1. (Naor and Naor [31]). A set S ⊆ Fnp of ngiven as input a system S of m degree-k n-variate poly- dimensional vectors is ε -biased if for all non-zero v ∈ Fnp
nomial equations over F pd , together with an irreducible and all a ∈ F p ,polynomial P(X) of degree d in F p [X], outputs an equiv[]
alent system S p of dm degree-k dn-variate equations overPr ∑ ri vi = a ∈ (1/p − ε , 1/p + ε ).
F p . That is, S has a solution over F pd if and only if S p has
r∈S
i∈[n]
a solution over F p .
Proof. For every 0 ≤ ℓ ≤ (d − 1)k, compute degree(d − 1) polynomials Pℓ ∈ F p [X] such that X ℓ ≡ Pℓ (X)(mod P(X)). These Pℓ can be determined by simple polynomial division, in poly(d · k) time. Let xi be the ith variable in the system S; we intend to set xi to a value in F pd .
F pd is isomorphic to F p [X]/P, that is, the elements of F pd
can be thought of as equivalence classes of polynomials in
F p [X] modulo P(X). It is a basic fact that every elementd−1
ri X ℓ for ri ∈ F p
r of F p [X]/P can be written as r = ∑l=0
in a unique way. Thus, for each i ≤ n and 0 ≤ ℓ ≤ d − 1
d−1
xi,ℓ X ℓ . That
we can define xi,ℓ ∈ F p such that xi ≡ ∑l=0
is, we think of the value of xi as a d-dimensional vector with entries from F p , where xi,ℓ is the ℓth component of this vector. Consider now the product xi x j , wehave that xi x j ≡ ∑d−1
l1 ,l2 =0 xi,ℓ1 xi,ℓ2 Pℓ1 +ℓ2 . Since all Pℓ ’s are
fixed polynomials in F p [X], the coefficients of every X ℓ
are quadratic forms over the variables {xi,ℓ }0≤ℓ<d and{x j,ℓ }0≤ℓ<d .
In general, a product of k variables can be viewed as adegree-d polynomial of X, whose coefficients are degreek forms of {xi,ℓ }1≤i≤n,0≤ℓ<d . Therefore, a single degreek polynomial equation over the variables {xi }1≤i≤n overF pd can be viewed as a system of d degree-k polynomial
equations over the variables {xi,ℓ }1≤i≤n,0≤ℓ<d over F p .
Doing this for every equation in the input system increases
the number of variables and the number of equations by afactor of d, but reduces the underlying field from F pd toFp.

T HEOREM 4.1. (Alon, Goldreich, Håstad and PerFor every positive integer n and ε ∈alta [2]).
(0, 1/q), there is an ε -biased set Sn,ε ⊆ Fnp ofcardinality O(n3 (log32 p)/ε 3 ), constructible in timepoly(n(log2 p)/ε ).
We also need constructions of modulus-amplifying
polynomials:
L EMMA 4.1. (Beigel and Tarui [7]). For every positive
integer ℓ, the degree (2ℓ − 1) integer polynomialℓ−1 (Fℓ (y) = 1 − (1 − y)ℓ ∑j=0)ℓ+ j−1 jyj

has the property for all p ∈ Z:
• if y = 0 mod p, then Fℓ (y) = 0 mod pℓ ,• if y = 1 mod p, then Fℓ (y) = 1 mod pℓ .
In addition, for 0 ≤ i ≤ 2ℓ − 1, the coefficient of yi in Fℓ
has magnitude at most 2O(ℓ) .
Now we are ready to “derandomize” the probabilistic
polynomial constructions of Razborov and Smolensky as
follows. For a non-empty set S ⊆ Fnp and a positive integerℓ, define a polynomial pbS,ℓ (x) : Fnp → Z as(
pbS,ℓ (x) := ∑ Fℓ 

) p−1 ,∑ ri xir∈Si∈[n]
We may now directly combine the algorithm ofLemma 3.3 with the reduction of Lemma 3.4 to obtain improved savings for SysPolyEqs(q) when q is large where we regard F p as the set of integers {0, 1, . . . , p −compared to k and not prime. In particular, applying 1} ⊂ Z. Then, we have:
Lemma 3.4 and then solving the output instance using
L EMMA 4.2. Let S ⊆ Fnp be an ε -biased set and ℓ be a
Lemma 3.3 yields a proof of Theorem 1.1.
positive integer such that pℓ > |S|. Then:• If x = (0, 0, . . . , 0), then pbS,ℓ (x) = 0.
4 Deterministic Algorithms for Systems of• If x ̸= (0, 0, . . . , 0), then ( pbS,ℓ (x) mod pℓ ) ∈ ((1 −Polynomial Equations
1/p − ε )|S|, (1 − 1/p + ε )|S|).
We now show how to obtain a deterministic algorithm for

SysPolyEqs(q) that beats the naı̈ve O⋆ (qn ) time algorithm,
in particular we prove Theorem 1.2. We will first givesuch an algorithm for SysPolyEqs(p) for prime p. We
start with a “deterministic version” of the probabilistic
polynomial constructions of Razborov and Smolensky
following the lead of Chan and Williams [13]. We need aconstruction of small-biased spaces.

Proof. The first item is by the fact that Fℓ (0) = 0. The
second item is by the fact that for any a ̸= 0 mod p,a p−1 = 1 mod p holds and the definition of ε -biased set.
We are now prepared to give the deterministic algorithm
for fields of prime order:′

L EMMA 4.3. Let p be a prime. There is a deterministic Let M := (1 − 1/p)|S| and recall that ε := 1/(4 · pn ). For′
algorithm that, given an instance of SysPolyEqs(p) with m all y ∈ Fn−n
, we have thatppolynomial equationsof degree
at most k in n variables,()(RbS,ℓ (y) mod pℓ )/M ∈ (K(y) − 1/2, K(y) + 1/2).
1
+o(n)
n 1−
6/7
O(kp)
300kp
runs in time p·mand counts the
The algorithm computes a representation of (RbS,ℓ (y))
number of satisfying assignments for the system.
as a sum of monomials from the representations of
Proof. Let {p1 , p2 , . . . , pm } be an instance of {p1 , p2 , . . . , pm } by directly applying the definitions ofbbb
SysPolyEqs(p). We select an integer n′ = ⌊δ · n⌋, RS,ℓ (y) and QS,ℓ (y, a). The degree of (RS,ℓ (y)) is at most′′where the exact value of δ will be set at the end of the 4k(p − 1)n + O(kp log m). We will set n = δ n in such a
proof, strictly between 0 and 1, depending on k and q. way that′′′
Define a function Q : Fn−n× Fnp → F p as Q(y, a) = 1 ifp
M((1 − δ )n, 4k(p − 1)δ n) ≤ O⋆ (p(n−n )/7 ),p1 (y, a) = p2 (y, a) = · · · = pm (y, a) = 0 and Q(y, a) = 0′
otherwise. Also we define a function K : Fn−n
→ Z and that therefore the number of monomials in (RbS,ℓ (y))
p′′nas K(y) := |{a ∈ F p | Q(y, a) = 0}|. Note that K(y) is p(n−n )/7 · mO(kp) . Hence we′ can obtain the value ofrepresents the number of unsatisfying assignments when K(y) for all y ∈ Fnp in time pn−n +o(n) · mO(kp) by applying
the first n − n′ variables are fixed to y. If we have the Lemma 2.3 to RbS,ℓ (y).
′value of K(y) for all y ∈ Fn−n
, we can compute the
We now proceed to the running time analysis, for thispnumber of satisfying assignments to the input instance, we need to specify more precisely how the representation′i.e., pn − ∑y∈Fn−n′ K(y), in time poly(n) · pn−n .
of (RbS,ℓ (y)) as a sum of monomials is computed. Inp
In what follows, we show how to construct an integer particular, all polynomial additions and multiplications
polynomial in the same n − n′ variables as K(y), such that are performed using the naı̈ve addition and multiplication′for every y ∈ Fn−n
, K(y) can be efficiently determined algorithms, however, we make sure that whenever we arepfrom the value of the polynomial evaluated on y. For a multiplying two polynomials, at least one of them has
nonempty set S ⊆ Fmp and a positive integer ℓ, define the degree at most kq. Note that this is achievable, because all
bS,ℓ (y, a). Heremultiplications occur in the definition of Q
integer polynomialsa polynomial of degree at most k is taken to the (p − 1)th(
) p−1 power, resulting in a polynomial of degree at most kp.
Then Fℓ is applied to this polynomial. Note that Fℓ (t) canb
QS,ℓ (y, a) := ∑ Fℓ,
∑ ri · pi (y, a)be computed using the definition of Lemma 4.1 in such
r∈S
i∈[m]
a way that in any multiplication, at least one of the two
bS,ℓ (y, a).
RbS,ℓ (y) := ∑ Q
factors is either t or 1 − t. Thus, each multiplication takes′a∈Fnptime at mostHere we regard F p as the set of integers {0, 1, . . . , p − 1}and each pi as an integer polynomial whose coefficientsare from {0, 1, . . . , p − 1} in a natural way.
′

Let ε := 1/(4 · pn ), and construct an ε -biased set
S ⊆ Fmp using Theorem 4.1. We have that |S| is at most′′
m3 p3n +O(1) , and that S is constructed in O⋆ (pO(n ) ) time.
′Now, let ℓ be the smallest integer greater than |S|pn ,note that ℓ ≤ 4n′ + log m + O(1). By Lemma 4.2, for all′′y ∈ Fn−nand a ∈ Fnp , we have thatpQ(y, a) = 1 ⇒Q(y, a) = 0 ⇒bS,ℓ (y, a) = 0,Q
bS,ℓ (y, a) mod pℓ )(Q∈ ((1 − 1/p − ε )|S|, (1 − 1/p + ε )|S|).
′

Then, for all y ∈ Fn−n
, we havep(RbS,ℓ (y) mod pℓ )∈ ((1 − 1/p − ε )|S|K(y), (1 − 1/p + ε )|S|K(y)).

O⋆ (M(n, 4k(p − 1)n′ + O(kp log m))) · M(n, kp)≤ M(n, 4k(p − 1)n′ ) · (mn)O(kp) .
′bS,ℓ (y, a) is computed with O⋆ (|S|) ≤ O⋆ (p3n )Each Q
polynomial additions and multiplications, and (RbS,ℓ (y)) isbS,ℓ (y, a) over all pn′ choices of a. Hence, thethe sum of Q
total number of operations needed to construct (RbS,ℓ (y))′
is upper bounded by O⋆ (p4n ). Evaluating (RbS,ℓ (y)) using′
Lemma 2.3 takes time pn−n +o(n) ·mO(kp) , while construct′
ing |S|, which is done once, takes time O⋆ (pO(n ) ). Hencethe total running time is upper bounded by′′

pn−n +o(n) + pO(n )′+p4n · M(n − n′ , 4k(p − 1)n′ ) · (nm)O(kp)≤ p(1−δ )n+o(n) + pc·δ n+p4δ n · M((1 − δ )n, 4k(p − 1)δ n) · (nm)O(kp) .
′Here c is the constant in the big-Oh notation in the pO(n )term, c is independent of p and k.

We now discuss the choice of δ for different values ofp and k. We will always pick δ to be at less than 1/(c + 1)
and less than 1/5, thus the first term in the running
time will always be larger than the second. Further,
we have already constrained the choice of δ such that′M((1 − δ )n, 4k(p − 1)δ n) ≤ p(n−n )/7 . For such a δ , therunning time is upper bounded bychoices for the coefficients of P(X), and then testing
irreducibility by dividing P(X) by each polynomial in
F p [X] of degree at most d/2. Then transform the input
system using Lemma 3.4 to an equivalent system of km
degree d polynomial equations over kn variables in F p ,and use Lemma 4.3 to solve this system.

p(1−δ )n+o(n) + p4δ n · p(1−δ )/7 · (nm)O(kp) ≤ p(1−δ )n+o(n) .

5 A Degree Reduction Algorithm

In this section we prove Theorems 1.3 and 1.4. SpecifWe first consider the case that p ≥ (2e)7 . We set δ = ically, we present algorithms for a generalization of
SysPolyEqs(2), where each pi is a polynomial of the form
1/(10ekp6/7 ), then we have that
M((1 − δ )n, 4k(p − 1)δ n) ≤ M((1 − δ )n, 5kpδ n(1 − δ ))si ti, j
((
)
)
(5.1)
pi (x) = ai + ∑ ∏ bi, j,k + ∑ xl 
n + 5kpδ n 1−δ
⋆(1−δ )nj=1 k=1l∈Ui, j,k
≤ (e + 5ekpδ )≤Onfor ai , bi, j,k ∈ {0, 1}, si ,ti, j ≥ 1 and 0/ ̸= Ui, j,k ⊆{1, 2, . . . , n}. Let s := ∑i si and u := ∑i, j,k |Ui, j,k | de1
7
note
the number of products and the size respectively.
Suppose now that p < (2e) , we set δ = kp6/7 ·300 . WeWhen
the polynomials in the input system are given in thehave thatform
5.1,
we refer to the problem as GenSysPolyEqs(2).
(()1−δ )
Our
algorithm
works by reducing systems of polynoδ
n
n
+
5kp
M((1 − δ )n, 4k(p − 1)δ n) ≤ O⋆
mial
equations
overF2 where each polynomial is in the
n
form
5.1
to
systemsof polynomial equations over F2


1−δ
(
p1/7 )
wherethedegreeofthepolynomials of the output sysn + n 60
≤ O⋆ 
tem
dependsonthenumberof products in the input sysn
tem. This reduction together with Theorems 1.1 and 1.2will complete the proofs of Theorems 1.3 and 1.4, respec() () p1/7 (1−δ )n
1/7
60
p
60
tively.

⋆ 

≤O 
1+
· 1 + 1/760pNote that because we are working in F2 , xℓd = xℓ for
all d ≥ 1, and that therefore the degree of a monomial is(()(1−δ )n )equal to the number of variables in it. The degree of a
⋆
1/7
≤O
p
.
polynomial pi is at most maxti, j , however it is possiblethat it is actually less. In this section we will abuse
The last transition was verified by explicitely comparing terminology and for each i refer to the degree of thethe two sides for every integer p between 2 and (2e)7 . polynomial p as deg(p ) := maxt .
iii, jThis completes the proof.
Tools from Linear Algebra. We need the following stanLemma 4.3 only works for prime fields, however, by dard notions and properties of linear independence of F2 .
combining Lemma 4.3 with the reduction of Lemma 3.4, Let V be a set of vectors {v1 , v2 , . . . , vt } ⊆ {0, 1}n . We say
we obtain an algorithm that works for all fields. More V is linearly dependent if there exists a non-zero vector
concretely, we are now in position to prove Theorem 1.2. (a1 , a2 , . . . , at ) ∈ {0, 1}t such that ∑ti=1 ai vi = (0, 0, . . . , 0)
holds. Otherwise, V is linearly independent. If V is linTheorem 1.2 (restated). Let q = pd for a prime p andearly independent and V ∪ {v} is linearly dependent for
integer d ≥ 1. There is a deterministic algorithm that,all v ∈ {0, 1}n \ V , then V is maximally linearly indepengiven an instance of SysPolyEqs(q) with m polynomial
dent. The rank of V , denoted by rank(V ), is the maximum
equations) at most k in n variables, runs in cardinality of a linearly independent subset of V . For any( of degree
1
+o(n)
n 1−
′
300kq6/7d· mO(kq) and counts the number maximally linearly independent subset V of V , the carditime q′ is equal to rank(V ).
nalityofVof satisfying assignments for the system.
Let V be a subset of {0, 1}n and V ′ be a linearly
Proof. Given as input a system of m degree d polynomial independent subset of {0, 1}n . The rank of V relative toequations over n variables in Fq , find in time pO(d) = qO(1) V ′ is the maximum cardinality of a subset V ′′ of V suchan irreducible polynomial P(X) in F p [X] of degree d. that V ′ ∪V ′′ is linearly independent. Note that any vector
This can be done by going over all of the at most pd in V can be written as a linear combination of vectors in′≤ p(1−δ )n/7 = p(n−n )/7 .

V ′ ∪ V ′′ . In what follows, it is convenient to identify thevector v ∈ {0, 1}n with the set Sv = {i ∈ [n] | vi = 1} andthe linear form L = ∑ni=1 vi xi . Thus, we use terms suchas linearly independent and rank for a set of subsets of[n] or a set of linear forms in a natural way. For linear
forms L1 , L2 , . . . , Lt and a1 , a2 , . . . , at ∈ {0, 1}, we identify
the system of linear equations {Li = ai }ti=1 with the affine
subspace {x ∈ {0, 1}n | L1 = a1 , L2 = a2 , . . . , Lt = at }. The
following lemma gives a way to reduce the degree ofpolynomials all of whose products of sums of variables
have “low rank.”
L EMMA 5.1. (Degree reduction relative to a system of
linear equations). Let U1 ,U2 , . . . ,Ut be subsets of [n] and′L1 , L2 , . . . , Lt ′ be linear forms such that {Li }ti=1 is linearly′
independent and the rank of {Ui }ti=1 relative to {Li }ti=1
is d. Then, for all a1 , a2 , . . . , at ′ , b1 , b2 , . . . , bt ∈ {0, 1},
there exists a(polynomial p) of degree at most d such that′p(x) = ∏tk=1 bk + ∑l∈Uk xl holds for all x ∈ {Li = ai }ti=1 .
Proof. Let V be a linearly independent subset{S1 , S2 , . . . , Sd } of {Ui }ti=1 such that the rank of V′
relative to {Li }ti=1 is d. By the definition of the rankof a set relative to a set, each Ui can be written as′a linear combination of vectors in( V ∪ {Li }ti=1 .) Thist
implies that we can write ∏k=1 bk + ∑l∈Uk xl as afunction of S1 , S2 , . . . , Sd , L1 , L2 , . . . , Lt ′ .
By setting
L1 = a1 , L2 = a2 , . . . , Lt ′ = at ′ and using the fact thatevery function in d variables can be written as a degree-dpolynomial, we complete the proof.
Simplification of systems of polynomial equations. Before describing our main algorithm, we introduce a procedure that simplifies instances of GenSysPolyEqs(2).
Let P = {p1 , p2 , . . . , pm } be an instance of GenSysPolyEqs(2). Let deg(P) = max deg(pi ). We partition P into P1 and P2 such that P1 = {p ∈ P| deg(p) ≤1} and P2 = {p ∈ P| deg(p) ≥ 2}. Note that we cancheck whether P1 is satisfiable or not in polynomial time
via Gaussian elimination. In what follows, we assumepi (x) = ai + ∑ j∈Ui x j if deg(pi ) ≤ 1 and


si

ti, j

pi (x) = ai + ∑ ∏ bi, j,k +j=1 k=1∑ xl 

l∈Ui, j,k

if deg(pi ) ≥ 2. Given a positive integer d, we define theprocedure Simplify(P, d) as follows:
1. Simplify P1 : Assume P1 = {p1 , p2 , . . . , pm′ }. First,
check whether a system of linear equations p1 =p2 = · · · = pm′ = 0 is satisfiable. If the system
is not satisfiable, return unsatisfiable, and continue
otherwise. Select a maximally linearly independent′
subset V of {Ui }m
i=1 . Redefine P1 := {pi }Ui ∈V .

2. Simplify P2 with P1 : Assume P1 = {p1 , p2 , . . . , pm′ }and P2 = {pm′ +1 , pm′ +2 , . . . , pm }. For m′ + 1 ≤ i ≤ m,
1 ≤ j ≤ si and 1 ≤ k ≤ ti, j , if Ui, j,k can be written′
as a linear combination of vectors in {Ui }m
i=1 as′Ui, j,k = ∑m
i=1 ciUi for some c1 , c2 , . . . , cm′ ∈ {0, 1},′
replace ∑l∈Ui, j,k xl by ∑m
i=1 ci ai . If deg(pi ) ≤ 1 forsome i, m′ + 1 ≤ i ≤ m after the substitution, remove
pi from P2 , add it to P1 and go back to Step 1.
3. Degree Reduction:
Again, assume P1 ={p1 , p2 , . . . , pm′ } and P2 = {pm′ +1 , pm′ +2 , . . . , pm }.
For m′ + 1 ≤ i ≤ m and 1 ≤ j ≤ si , if the rank of
ti, j
m′
with
{Ui, j,k }k=1
( respect to {Ui)}i=1 is at most d,ti, jbi, j,k + ∑l∈Ui, j,k xl as a polynomial
rewrite ∏k=1
of degree at most d by Lemma 5.1. If deg(pi ) ≤ 1
for some i, m′ + 1 ≤ i ≤ m after the above rewriting,remove pi from P2 , add it to P1 and go back to Step
1.

Let P′ be the simplified instance obtained by applying Simplify to P. The following is true: (P1) The
number of satisfying assignments for P is equal to thatfor P′ . (P2) Partition the resulting instance P′ into
P1′ and P2′ and assume P1′ = {p1 , p2 , . . . , pm′ } and P2′ =′{pm′ +1 , pm′ +2 , . . . , pm }. Then, (i) {Ui }mi=1 is linearly in′dependent, and (ii) for m + 1 ≤ i ≤ m and 1 ≤ j ≤ si , weti, jhave either ti, j ≤ d or the rank of {Ui, j,k }k=1with respect′mto {Ui }i=1 is at least d + 1.
The algorithm and its analysis. We now describe thealgorithm Degree-Reduction(P, d), which we will use toprove Theorems 1.3 and 1.4. We first finish the proof of
Theorem 1.3 and then describe the necessary adjustments
to prove Theorem 1.4.

1. Run Simplify(P, d).
2. If deg(P) ≤ d, assume P1 = {p1 , p2 , . . . , pm′ } andselect an arbitrary subset V of {0, 1}n such that′{Ui }mi=1 ∪ V is maximally linearly independent, i.e.,
has rank n. Rewrite each variable xi as a linear′
combination of vectors in {Ui }m
i=1 ∪ V . We regard
each vector in V as a formal variable and each vector
Ui as the constant a(i . Apply Theorem) 1.1 to the′resulting instance in n − rank({Ui }mi=1 ) variables.
3. If deg(P) > d, assume P1 = {p1 , p2 , . . . , pm′ } and select arbitrary i, j′ , m′ + 1 ≤ (i ≤ m, 1 ≤ j′ ≤ si ,)suchti, jsi
that pi (x) = ai + ∑ j=1 ∏k=1 bi, j,k + ∑l∈Ui, j,k xl and
t ′

i, j
ti, j′ > d. Select an arbitrary subset V of {Ui, j′ ,k }k=1

′of size d such that V ∪ {Ui }mi=1 is linearly independent. Defineqi (x) :=∏ bi, j,k + ∑ xl  ,Ui, j,k ∈Vl∈Ui, j,k



(
)
1
1
n
= O⋆ 2(1− 5d )n · (1 + 2−d (1− 5d ) )s+ d
{
(
(
1
1
n )})
≤ O⋆ 2(1− 5d )n · exp 2−d (1− 5d ) s +
(
) d
1 n
1− 5d
⋆
4s/2d−1/5()≤ O poly(u) · 2·2,

where we assume s ≥ n/d. We set+c( d :=1 )2 log(s/n)
4sfor
sufficiently
large
c
>
0,
then
1
−
n
+
≤
5d
ri (x) := ai +2d−1/5
∑ ′
∑
(
)
1
1
k=1
l∈U
1≤ j≤si , j̸= ji, j,k1 − 10 log(s/n)+5c + (s/n)2c−3 n. This completes the proofof Theorem 1.3.
Define instances PL := {P \ {pi }} ∪ {qi , ri }, andWe see that (1) Simplify does not change the number
Then, of satisfying assignments by Property P-1, and (2) each
PR := P ∪ {bi, j,k + ∑l∈Ui, j,k xl }Ui, j,k ∈V .
run
Degree-Reduction(PL , d)andDegree- branching of Degree-Reduction only partitions the soluReduction(PR , d) recursively.
tion space. This implies that if we replace Theorem 1.1
by Theorem 1.2 in Step 2 of Degree-Reduction and add
The correctness of Degree-Reduction is guaranteed since the number of satisfying assignments of PL and that of PR
P is satisfiable if and only if at least one of PL and PR is sat- in Step 3, we obtain Theorem 1.4.
isfiable. This is because in Step 3, instances PL and PR correspond to conditions qi (x) = 0 and qi (x) = 1 respectively. 6 Concluding Remarks
Note that we can choose V in Step 3 due to Property (P2)We have shown how multivariate systems of polynomial(ii) of Simplify. In what follows, we give the running time
equations can be solved faster than exhaustive search inanalysis of Degree-Reduction(P, d). The overall strucvery generic settings. There are two natural extensions
ture is the same as the analysis of Schuler’s width reducthat we have not yet been able to crack:tion algorithm for SAT of CNF formulas in [12].
Is there an algorithm for SysPolyEqs(q) with a better
We regard the execution of Degree-Reduction as aruntime exponent? Our savings over exhaustive searchrooted binary tree T . The root of T is labeled with an input
for SysPolyEq(pd ) in the exponent is n/O(k) for degreeinstance P. For each node labeled with Q, its left (right,
log log q−log 4ek
4ek
)
log q
resp.) child is labeled with QL (QR , resp.) as defined in k polynomials when p ≤ 2 , and n · O(
otherwise.
Can
oneachievesavingsn/O(k)
even
for
large
Step 3 of Degree-Reduction. If deg(Q) ≤ d holds, then
the node labeled with Q is a leaf. Let us consider a path p compared to k? Can such savings be achieved by ap from the root to a leaf v labeled with Q. We denote by deterministic algorithm? We remark that removing the
L and R the number of left and right children p selects to factor of 1/k from the savings entirely would refute thereach v. We see that (1) L ≤ s since the number of products Strong Exponential Time Hypothesis (k-SAT can easily
with degree more than d is at most s, (2) R ≤ n/d since be embedded into degree-k instances of SysPolyEqs(2)).
a right branch increases the rank of P1 (as a set of linear
Is there an algorithm for SAT of large-depth arithforms) by d and the rank of P1 cannot be larger than n, metic circuits over F p ? Arbitrary arithmetic circuits?
and (3) Q is defined over at most n − dR variables in the Our algorithm for GenSysPolyEqs(2) already solves thesense of Step 2 of Degree-Reduction. Furthermore, the SAT problem for ΠΣΠΣ circuits which is a considernumber of leaves that are(reachable
by exactly R times of able generalization of CNF-SAT. By results of Agrawal)
right branches is at most s+R.
Let
T (n, m, d) denote the and Vinay [1] who reduce arbitrary small low-degree cirRrunning time of the algorithm of Theorem 1.1 on instances cuits to subexponential-size ΣΠΣΠ circuits, we can alof SysPolyEqs with m polynomial equations of degree at ready conclude a non-trivial SAT algorithm for any F2 most d in n variables. We can upper bound the running arithmetic circuit of degree less than n2−ε (by a randomtime of Degree-Reduction as follows:ized reduction).
ti, j∏ bi, j,k +

( n (

)
)
s+R
O
∑ R · T (n − dR, m, d)
R=0
( n (
)
)
d
1 (n−dR)
s+R
1− 5d
⋆
(
)
≤ O
∑ R ·2R=0)(s+ n ()
d1 (n−dR)s + dn
1− 5d
⋆
(
)
≤ O
∑ R ·2R=0⋆dxl  .

Acknowledgments. The fourth author thanks Timothy
Chan for helpful discussions on an earlier phase of thiswork.
References[1] M. Agrawal and V. Vinay. Arithmetic circuits: A chasmat depth four. In Proceedings of the 49th Annual IEEE

Symposium on Foundations of Computer Science (FOCS),
pages 67–75, 2008.
[2] N. Alon, O. Goldreich, J. Håstad, and R. Peralta. Simple
construction of almost k-wise independent random variables. Random Struct. Algorithms, 3(3):289–304, 1992.
[3] G. Bard. Algebraic cryptanalysis. Springer Science &Business Media, 2009.
[4] G. V. Bard, N. Courtois, and C. Jefferson. Efficientmethods for conversion and solution of sparse systems of
low-degree multivariate polynomials over GF(2) via SATsolvers. IACR Cryptology ePrint Archive, 2007:24, 2007.
[5] M. Bardet, J. Faugère, B. Salvy, and P. Spaenlehauer. On
the complexity of solving quadratic Boolean systems. J.
Complexity, 29(1):53–75, 2013.
[6] R. Beigel. The polynomial method in circuit complexity.
In Proceedings of the 8th Annual Structure in Complexity
Theory Conference, pages 82–95, 1993.
[7] R. Beigel and J. Tarui. On ACC. Computational Complexity, 4:350–366, 1994.
[8] A. Bhowmick and S. Lovett. Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory. Electronic Colloquium
on Computational Complexity (ECCC), TR15-22, 2015.
[9] A. Björklund, T. Husfeldt, and M. Koivisto. Set partitioning via inclusion-exclusion. SIAM J. Comput., 39(2):546–
563, 2009.
[10] A. Björklund, R. Pagh, V. V. Williams, and U. Zwick.
Listing triangles. In Proceedings of the 41st International
Colloquium on Automata, Languages, and Programming(ICALP), Part I, pages 223–234, 2014.
[11] M. Bronstein, A. M. Cohen, H. Cohen, D. Eisenbud,
B. Sturmfels, A. Dickenstein, and I. Z. Emiris. Solving
Polynomial Equations: Foundations, Algorithms, and Applications. Springer, 2005.
[12] C. Calabro, R. Impagliazzo, and R. Paturi. A duality between clause width and clause density for SAT. In Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC), pages 252–260, 2006.
[13] T. M. Chan and R. Williams. Deterministic APSP,
orthogonal vectors, and more: Quickly derandomizing
Razborov-Smolensky. In Proceedings of the 27th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 1246–1255, 2016.
[14] M. Cheraghchi, E. Grigorescu, B. Juba, K. Wimmer,
and N. Xie. AC0 ◦MOD2 lower bounds for the Boolean
inner product. In Proceedings of the 43rd International
Colloquium on Automata, Languages and Programming(ICALP), pages 35:1–35:14, 2016.
[15] G. Cohen and I. Shinkar. The complexity of DNF of
parities. In Proceedings of the 2016 ACM Conference on
Innovations in Theoretical Computer Science, pages 47–
58, 2016.
[16] N. Courtois, A. Klimov, J. Patarin, and A. Shamir. Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In Proceedings of the 19thInternational Conference on the Theory and Applicationof Cryptographic Techniques (EUROCRYPT), pages 392–
407, 2000.
[17] J. Ding, J. E. Gower, and D. Schmidt. Multivariate Public

Key Cryptosystems, volume 25 of Advances in Information
Security. Springer, 2006.
[18] J. Håstad. Satisfying degree-d equations over GF[2]n .
Theory of Computing, 9:845–862, 2013.
[19] M. A. Huang and Y. Wong. Solving systems of polynomial
congruences modulo a large prime (extended abstract). In
Proceedings of 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 115–124, 1996.
[20] R. Impagliazzo, W. Matthews, and R. Paturi. A satisfiability algorithm for AC0 . In Proceedings of the 23rd Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 961–972, 2012.
[21] Z. Jafargholi and E. Viola. 3SUM, 3XOR, triangles.
Algorithmica, 74(1):326–343, 2016.
[22] N. Kayal. Derandomizing some number-theoretic andalgebraic algorithms. PhD thesis, Indian Institute ofTechnology Kanpur, 2006.
[23] K. S. Kedlaya and C. Umans. Fast polynomial factorization and modular composition. SIAM J. Comput.,40(6):1767–1802, 2011.
[24] S. Kopparty and S. Srinivasan. Certifying polynomials
for AC0 [⊕] circuits, with applications. In Proceedingsof the 32nd IARCS Annual Conference on Foundations ofSoftware Technology and Theoretical Computer Science(FSTTCS), pages 36–47, 2012.
[25] S. Kopparty and S. Yekhanin. Detecting rational points on
hypersurfaces over finite fields. In Proceedings of the 23rd
Annual IEEE Conference on Computational Complexity(CCC), pages 311–320, 2008.
[26] A. G. B. Lauder and D. Wan. Counting points on varieties
over finite fields of small characteristic. In J. P. Buhler
and P. Stevenhagen, editors, Algorithmic Number Theory:
Lattices, Number Fields, Curves and Cryptography, pages
579–612. Cambridge University Press, 2008.
[27] F. Le Gall. Faster algorithms for rectangular matrix
multiplication. In Proceedings of the 53rd Annual IEEE
Symposium on Foundations of Computer Science (FOCS),
pages 514–523, 2012.
[28] C. Lu. Hitting set generators for sparse polynomials overany finite fields. In Proceedings of the 27th Conference on
Computational Complexity (CCC), pages 280–286, 2012.
[29] W. G. Matthews. A satisfiability algorithm for constantdepth Boolean circuits with unbounded fan-in gates. PhD
thesis, UC San Diego, 2011.
[30] H. Miura, Y. Hashimoto, and T. Takagi. Extended algorithm for solving underdefined multivariate quadratic
equations. In Proceedings of the 5th International Workshop on Post-Quantum Cryptography (PQCrypto), pages
118–135, 2013.
[31] J. Naor and M. Naor. Small-bias probability spaces:
Efficient constructions and applications. SIAM J. Comput.,
22(4):838–856, 1993.
[32] R. Paturi, P. Pudlák, M. E. Saks, and F. Zane. An
improved exponential-time algorithm for k-SAT. J. ACM,
52(3):337–364, 2005.
[33] A. Razborov. Lower bounds on the size of bounded-depth
networks over a complete basis with logical addition.
Mathematical Notes of the Academy of Sci. of the USSR,
41(4):333–338, 1987.

[34] R. Schuler. An algorithm for the satisfiability problem
of formulas in conjunctive normal form. J. Algorithms,
54(1):40–44, 2005.
[35] R. Smolensky. Algebraic methods in the theory of lower
bounds for Boolean circuit complexity. In Proceedings ofthe 19th Annual ACM Symposium on Theory of Computing(STOC), pages 77–82, 1987.
[36] B. Sturmfels. Solving Systems of Polynomial Equations.
American Mathematical Society, 2002.
[37] V. Vassilevska Williams and R. Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput., 42(3):831–854, 2013.
[38] R. Williams. A casual tour around a circuit complexity
bound. SIGACT News, 42(3):54–76, 2011.
[39] R. Williams. Nonuniform ACC circuit lower bounds. J.
ACM, 61(1):2, 2014.
[40] R. Williams. The polynomial method in circuit complexity
applied to algorithm design (invited talk). In Proceedingsof the 34th International Conference on Foundation ofSoftware Technology and Theoretical Computer Science(FSTTCS), pages 47–60, 2014.
[41] A. R. Woods. Unsatisfiable systems of equations, over afinite field. In Proceedings of the 39th Annual Symposium
on Foundations of Computer Science (FOCS), pages 202–
211, 1998.
[42] B. Yang and J. Chen. Theoretical analysis of XL oversmall fields. In Proceedings of the 9th AustralasianConference on Information Security and Privacy (ACISP),
pages 277–288, 2004.