Plaintext
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 185–188
www.theoryofcomputing.org
NOTE
Computing Polynomials
with Few Multiplications
Shachar Lovett∗
Received: June 19, 2011; published: September 16, 2011.
Abstract: It is a folklore result in arithmetic complexity that the number of multiplication
gates required to compute a worst-case n-variate polynomial of degree d is at least
q
n+d
Ω d ,
even if addition gates are allowed to compute arbitrary linear combinations of their inputs.
In this note we complement this by an almost matching upper bound, showing that for any
n-variate polynomial of degree d over any field,
q
n+d
d · (nd)O(1)
multiplication gates suffice.
ACM Classification: F.1.3
AMS Classification: 68Q25
Key words and phrases: arithmetic circuits, multiplications
1 Introduction
Arithmetic complexity is a branch of theoretical computer science which studies the minimal number
of operations (additions and multiplications) required to compute polynomials. A natural model of
∗ Supported by NSF grant DMS-0835373.
2011 Shachar Lovett
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2011.v007a013
S HACHAR L OVETT
computation in these settings is an arithmetic circuit, where the inputs are variables x1 , . . . , xn , gates
correspond to the +, × operations and multiplication by field elements, and the output gate computes
the required polynomial. The complexity measures associated with arithmetic circuits are their size and
depth. We refer the reader to [3] for an extensive survey on arithmetic circuits.
In this note we focus on the minimal number of multiplications required to compute a polynomial,
where additions of polynomials and multiplication by field elements are free. To this end, we consider a
non-standard model of arithmetic circuits where addition gates can compute arbitrary linear combinations
of their inputs (instead of just their sum). We assume both multiplication and addition gates have
unbounded fan-in. For a polynomial f we define its multiplicative complexity, denoted M( f ), to be the
minimal number of multiplication gates required to compute f in this non-standard model.
Consider polynomials of degree d in n variables over a field F. (In this note, we write “degree-d
polynomials” as a shorthand for “polynomials of total degree at most d.”) The number of possible
monomials of such a polynomial is n+d
d . It is a folklore result in arithmetic complexity (see, e. g., [1,
Theorem 4.2]) that the number of multiplications required to compute some n-variate polynomial of
degree d is at least the square root of this number.
Theorem 1.1 (Theorem 4.2 in [1]). Let F be a field and n, d be two natural q numbers.
Then there exists
n+d
an n-variate polynomial f (x1 , . . . , xn ) of degree d for which M( f ) ≥ Ω d .
Hrubeš and Yehudayoff [2] exhibit similar lower bounds even if one considers only polynomials with
0-1 coefficients.
Theorem 1.2 ([2]). Let F be a field and n, d be two natural numbers. Then there exists
an n-variate
q
n+d
polynomial f (x1 , . . . , xn ) of degree d with 0-1 coefficients for which M( f ) ≥ Ω d .
The aim of this note is to complement these lower bounds by an almost matching upper bound.
Theorem 1.3. Let F be a field and n, d be twoq natural numbers. Let f (x1 , . . . , xn ) be any n-variate
n+d
polynomial of degree d over F. Then M( f ) ≤ d · (nd)O(1) .
To the best of our knowledge, the best previous upper bound on the number of multiplications was
M( f ) ≤ O n1 n+d
d
(see the discussion following Theorem 4.4 in [1]). We note that the circuit constructed in Theorem 1.3
has the following additional features, which can be immediately verified from the construction:
(1) It is a depth-4 circuit.
(2) If f has 0-1 coefficients, or if the field is of size at most poly(n), then the bound holds also in the
standard model of arithmetic circuits where addition gates compute the sum of their inputs (instead
of linear combinations of their inputs).
(3) If f is a real polynomial with positive coefficients, then the circuit computing f is monotone (i. e.,
all coefficients in the addition gates are positive).
We now turn to the proof.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 185–188 186
C OMPUTING P OLYNOMIALS WITH F EW M ULTIPLICATIONS
2 Proof of Theorem 1.3
We first fix some notation: let N := {0, 1, . . .} and [n] := {1, . . . , n}. We identify monomials in x1 , . . . , xn
with their exponent vectors e ∈ Nn , where we use the shorthand xe := x1e1 . . . xnen . We denote the set of
all n-variate degree-d monomials by M(n, d) := {e ∈ Nn : ∑ ei ≤ d}. Note that |M(n, d)| = n+d
d . The
weight of a monomial is |e| := ∑ ei .
The main idea is to cover the set M(n, d) of monomials by few sums of pairs of sets. For sets
A, B ⊆ Nn denote their sum by A + B := {a + b | a ∈ A, b ∈ B}.
Claim 2.1. Let {(Ai , Bi )}i∈[k] be pairs of subsets of Nn such that M(n, d) ⊆ ki=1 (Ai + Bi ). Then for any
S
n-variate polynomial f (x1 , . . . , xn ) of degree d we have M( f ) ≤ 2 ∑ki=1 (|Ai | + |Bi |).
Proof. Let f (x) = ∑e∈M(n,d) λe xe be an n-variate polynomial of degree d. First compute all monomials xe
for e ∈ A1 , B1 , . . . , Ak , Bk . This can be done with ∑ki=1 (|Ai |+|Bi |) multiplications (recall that multiplication
gates have unbounded fan-in). By assumption, for each monomial e ∈ M(n, d) there exists i ∈ [k] such that
e ∈ Ai + Bi . For i ∈ [k], e0 ∈ Ai , e00 ∈ Bi define δi,e0 ,e00 ∈ {0, 1} as follows: enumerate the triples (i, e0 , e00 )
in some order; for a triple (i, e0 , e00 ), if the sum e0 + e00 never occurred in a previous triple, set δi,e0 ,e00 = 1,
otherwise set δi,e0 ,e00 = 0. We thus have
0
00
f (x) = ∑ki=1 ∑e0 ∈Ai xe × ∑e00 ∈Bi λe0 +e00 δi,e0 ,e00 · xe .
This representation allows one to compute f using only ∑ki=1 |Ai | additional multiplications.
We thus need to construct small sets {(Ai , Bi )} whose pairwise sums cover M(n, d). We will construct
these sets from polynomials in ∼ n/2 variables of degree ∼ d/2.
For a subset S ⊆ [n] of variables denote by M(S, d) the set of all monomials of degree at most d in
the variables of S. Clearly |M(S, d)| = |S|+d
d . In the following we identify [n] := Zn , i. e., we consider
indices modulo n. For i, j ∈ [n] define the interval [i, j] := {i, i + 1, . . . , j} ⊆ Zn .
Claim 2.2. Let n be odd and d be even. For i = 1, . . . , n, set Ai := M([i, i + (n − 1)/2], d/2) and
Bi := M([i − (n − 1)/2, i], d/2). Then M(n, d) ⊆ ni=1 (Ai + Bi ).
S
Proof. Let e ∈ M(n, d). We need to show that e ∈ Ai + Bi for some i ∈ [n]. Let m := (n − 1)/2. For
i ∈ [n] define the partial sum wi := ∑m
`=1 ei+` where indices are taken modulo n. Note that
wi + wi+m = |e| − ei ≤ d − ei . (1)
We first claim that if wi , wi+m ≤ d/2 then e ∈ Ai + Bi . We then proceed to show such an index i indeed
exists.
Assume first that wi , wi+m ≤ d/2. We will construct e0 ∈ Ai , e00 ∈ Bi such that e = e0 + e00 . By
Equation (1), we can decompose ei = e0i + e00i such that e0i , e00i ≥ 0, wi + e0i ≤ d/2 and wi+m + e00i ≤ d/2.
For j 6= i set e0j = e j , e00j = 0 if j ∈ [i, i + m] \ {i}; and e0j = 0, e00j = e j if j ∈ [i − m, i] \ {i}.
To conclude the proof we need to show that there exists i for which wi , wi+m ≤ d/2. Assume
this is not the case. Then there exists j for which w j > d/2. But then w j+m < d/2 by Equation (1).
Therefore there must exist i such that wi ≤ d/2 and wi−1 ≥ d/2. This concludes the proof since
wi+m = |e| − ei+m − wi−1 ≤ d/2 by Equation (1).
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 185–188 187
S HACHAR L OVETT
We now conclude with the proof of Theorem 1.3.
Proof of Theorem 1.3. Let f (x) be an n-variate polynomial of degree d. Let n0 ≥ n, d 0 ≥ d be minimal
such that n0 is odd and d 0 is even. By Claim 2.2 we can find sets Ai , Bi , i ∈ [n0 ] such that
n0
M(n, d) ⊆ M(n0 , d 0 ) ⊆ ∑ (Ai + Bi ) ,
i=1
and such that
0 !! s
(n + 1)/2 + d 0 /2 d n1/2
n+d
|Ai |, |Bi | = ≤ O max , · .
d 0 /2 n5/4 d 3/4 d
q
d n3/2 n+d
Thus by Claim 2.2 we have M( f ) ≤ O max n1/4 , d 3/4 · d , justifying the claim.
Acknowledgements I thank Avi Wigderson, Amir Shpilka, and Neeraj Kayal for helpful discussions. I
thank the anonymous reviewers for a careful reading of this note and in particular for a simplification of
Claim 2.2.
References
[1] X I C HEN , N EERAJ K AYAL , AND AVI W IGDERSON: Partial derivatives in arithmetic complexity
(and beyond). Found. Trends Theor. Comput. Sci. To appear. 186
[2] PAVEL H RUBE Š AND A MIR Y EHUDAYOFF: Arithmetic complexity in ring extensions. Theory of
Computing, 7(1):119–129, 2011. http://www.theoryofcomputing.org/articles/v007a008.
[doi:10.4086/toc.2011.v007a008] 186
[3] A MIR S HPILKA AND A MIR Y EHUDAYOFF: Arithmetic circuits: A survey of recent results and open
questions. Found. Trends Theor. Comput. Sci., 5:207–388, March 2010. [doi:10.1561/0400000039]
186
AUTHOR
Shachar Lovett
member, School of Mathematics
Institute for Advanced Study, Princeton, NJ
slovett math ias edu
http://www.math.ias.edu/~slovett
ABOUT THE AUTHOR
S HACHAR L OVETT graduated from the Weizmann Institute of Science in 2010; his advi-
sors were Omer Reingold and Ran Raz. He is interested in the theory of computing,
combinatorics, and coding theory, and in particular in the interplay between structure,
randomness, and pseudo-randomness.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 185–188 188