[PDF] Computing Polynomials with Few Multiplications

View - Download Computing Polynomials with Few Multiplications

Previous PDF

Next PDF

THEORY OFCOMPUTING, Volume 7 (2011), pp. 185-188

www.theoryofcomputing.orgNOTE

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-casen-variate polynomial of degreedis at least W 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 degreedover 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

SHACHARLOVETTcomputation in these settings is an arithmetic circuit, where the inputs are variablesx1;:::;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 ofmultiplicationsrequired 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 polynomialfwe define itsmultiplicative complexity, denotedM(f), to be the minimal number of multiplication gates required to computefin this non-standard model. Consider polynomials of degreedinnvariables over a fieldF. (In this note, we write "degree-d polynomials" as a shorthand for "polynomials of total degree at mostd.") The number of possible monomials of such a polynomial isn+d d. It is a folklore result in arithmetic complexity (see, e.g., [1, Theorem 4.2]) that the number ofmultiplicationsrequired to compute somen-variate polynomial of degreedis at least the square root of this number.

Theorem 1.1

(Theorem 4.2 in [1]).LetFbe a field andn;dbe two natural numbers. Then there exists an n-variate polynomial f(x1;:::;xn)of degree d for which M(f)W q n+d d Hrubes and Yehudayoff [2] exhibit similar lower bounds even if one considers only polynomials with

0-1 coefficients.

Theorem 1.2

([2]).LetFbe a field andn;dbe two natural numbers. Then there exists ann-variate polynomial f(x1;:::;xn)of degree d with0-1coefficients for which M(f)W q n+d d The aim of this note is to complement these lower bounds by an almost matching upper bound.

Theorem 1.3.

LetFbe a field andn;dbe two natural numbers. Letf(x1;:::;xn)be anyn-variate polynomial of degree d overF. Then M(f)q n+d d(nd)O(1): To the best of our knowledge, the best previous upper bound on the number of multiplications was

M(f)O1n

n+d d

(see the discussion following Theorem 4.4 in [1]). We note that the circuit constructed inTheorem 1.3

has the following additional features, which can be immediately verified from the construction: (1)

It is a depth-4 circuit.

(2) Iffhas0-1coefficients, or if the field is of size at mostpoly(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) Iffis a real polynomial with positive coefficients, then the circuit computingfis monotone (i.e., all coefficients in the addition gates are positive).

We now turn to the proof.

THEORY OFCOMPUTING, Volume 7 (2011), pp. 185-188 186

COMPUTINGPOLYNOMIALS WITHFEWMULTIPLICATIONS

2 Proof of

Theor em

1.3 We first fix some notation: letN:=f0;1;:::gand[n]:=f1;:::;ng. We identify monomials inx1;:::;xn

with their exponent vectorse2Nn, where we use the shorthandxe:=xe11:::xenn. We denote the set of alln-variate degree-dmonomials byM(n;d):=fe2Nn:åeidg. Note thatjM(n;d)j=n+d d. The weight of a monomial isjej:=åei. The main idea is to cover the setM(n;d)of monomials by few sums of pairs of sets. For sets

A;BNndenote their sum byA+B:=fa+bja2A;b2Bg.

Claim 2.1.

Letf(Ai;Bi)gi2[k]be pairs of subsets ofNnsuch thatM(n;d)Ski=1(Ai+Bi). Then for any n-variate polynomial f(x1;:::;xn)of degree d we have M(f)2åki=1(jAij+jBij).

Proof.

Letf(x) =åe2M(n;d)lexebe ann-variate polynomial of degreed. First compute all monomialsxe

fore2A1;B1;:::;Ak;Bk. This can be done withåki=1(jAij+jBij)multiplications (recall that multiplication

gates have unbounded fan-in). By assumption, for each monomiale2M(n;d)there existsi2[k]such that e2Ai+Bi. Fori2[k];e02Ai;e002Bidefinedi;e0;e002 f0;1gas follows: enumerate the triples(i;e0;e00)

in some order; for a triple(i;e0;e00), if the sume0+e00never occurred in a previous triple, setdi;e0;e00=1,

otherwise setdi;e0;e00=0. We thus have f(x) =åki=1åe02Aixe0 e002Bile0+e00di;e0;e00xe00 This representation allows one to computefusing onlyåki=1jAijadditional multiplications. We thus need to construct small setsf(Ai;Bi)gwhose pairwise sums coverM(n;d). We will construct these sets from polynomials inn=2 variables of degreed=2. For a subsetS[n]of variables denote byM(S;d)the set of all monomials of degree at mostdin the variables ofS. ClearlyjM(S;d)j=jSj+d d. In the following we identify[n]:=Zn, i.e., we consider indices modulon. Fori;j2[n]define the interval[i;j]:=fi;i+1;:::;jg Zn.

Claim 2.2.

Letnbe odd anddbe even. Fori=1;:::;n, setAi:=M([i;i+(n1)=2];d=2)and

Bi:=M([i(n1)=2;i];d=2). ThenM(n;d)Sni=1(Ai+Bi).

Proof.

Lete2M(n;d). We need to show thate2Ai+Bifor somei2[n]. Letm:= (n1)=2. For i2[n]define the partial sumwi:=åm`=1ei+`where indices are taken modulon. Note that w i+wi+m=jejeidei:(1) We first claim that ifwi;wi+md=2thene2Ai+Bi. We then proceed to show such an indexiindeed exists. Assume first thatwi;wi+md=2. We will constructe02Ai;e002Bisuch thate=e0+e00. By Equation(1), we can decomposeei=e0i+e00isuch thate0i;e00i0,wi+e0id=2andwi+m+e00id=2. Forj6=isete0j=ej;e00j=0 ifj2[i;i+m]nfig; ande0j=0;e00j=ejifj2[im;i]nfig. To conclude the proof we need to show that there existsifor whichwi;wi+md=2. Assume this is not the case. Then there existsjfor whichwj>d=2. But thenwj+mSHACHARLOVETT

We now conclude with the proof of

Theorem

1.3

Proof of

Theor em

1.3 .Letf(x)be ann-variate polynomial of degreed. Letn0n;d0dbe minimal such thatn0is odd andd0is even. ByClaim 2.2 we can find sets Ai;Bi,i2[n0]such that

M(n;d)M(n0;d0)n

0 i=1(Ai+Bi); and such that jAij;jBij=(n0+1)=2+d0=2 d 0=2 O max dn

5=4;n1=2d

3=4!! s n+d d

Thus by

Claim 2.2 we ha veM(f)O maxdn

1=4;n3=2d

3=4 q n+d 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] XICHEN, NEERAJKAYAL,ANDAVIWIGDERSON: Partial derivatives in arithmetic complexity (and beyond).Found. Trends Theor. Comput. Sci.To appear.186 [2] PAVELHRUBES ANDAMIRYEHUDAYOFF: 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] AMIRSHPILKA ANDAMIRYEHUDAYOFF: 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

slovettmathiasedu http://www.math.ias.edu/ ~slovett

ABOUT THE AUTHOR

SHACHARLOVETTgraduated from theW eizmannInstitute 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. THEORY OFCOMPUTING, Volume 7 (2011), pp. 185-188 188quotesdbs_dbs47.pdfusesText_47

[PDF] multiplications des nombres relatifs

[PDF] multiplicité des critères pour rendre compte de la structure sociale

[PDF] Multiplié deux identités remarquables

[PDF] multiplier

[PDF] Multiplier des equations par (-1) et Diviser des equations par (-2)

[PDF] Multiplier des fractions

[PDF] multiplier des heures

[PDF] multiplier des nombres en écriture fractionnaire

[PDF] multiplier des nombres en écritures fractionnaires

[PDF] Multiplier des nombres positifs en écriture fractionnaire

[PDF] Multiplier des nombres positifs en écriture fractionnaire - 4eme

[PDF] Multiplier des nombres positifs en écriture fractionnaire - Maths

[PDF] multiplier deux fractions

[PDF] multiplier deux racines carrées identiques

[PDF] Multiplier et diviser des nombres relatifs en écriture fractionnaire