A Lower Bound for the Size of Syntactically Multil

ALowerBoundfortheSizeofSyntacticallyMultilinearArithmeticCircuitsRanRaz∗AmirShpilka†AmirYehudayoff‡AbstractWeconstructanexplicitpolynomialf(x1,...,xn),withcoefficientsin{0,1},suchthatthesizeofanysyntacticallymultilineararithmeticcircuitcomputingfisatleastΩ(n4/3/log2n).Thelowerboundholdsoveranyfield.1IntroductionArithmeticcircuitsarethestandardmodelforcomputingpolynomials(seeSection1.1fordefinition).Roughlyspeaking,givenasetofvariablesX={x1,...,xn},anarithmeticcircuitusesadditionsandmultiplicationstocomputeapolynomialfinthesetofvariablesX.Givenapolynomialf,weareinterestedinthenumberofoperationsneededtocomputef.ThebestlowerboundknownforthesizeofarithmeticcircuitsistheclassicalΩ(nlogn)ofStrassen[S73],andofBaurandStrassen[BS83].Provingbetterlowerboundsisanoutstandingopenproblem.Betterlowerboundsarenotknownevenforarithmeticcircuitsofdepth4(overfieldsofcharacteristicdifferentthan2).Inthispaper,wefocusonarestrictedclassofarithmeticcircuits,theclassofsyntactically∗FacultyofMathematicsandComputerScience,WeizmannInstitute,Rehovot,Israel,andMicrosoftResearch.Email:[e-mail]sfromtheBinationalScienceFoundation(BSF),theIsraelScienceFoundation(ISF),andtheMinervaFoundation.†FacultyofComputerScience,Technion,Israel.Email:[e-mail].‡FacultyofMathematicsandComputerScience,WeizmannInstitute,Rehovot,Israel.Email:[e-mail]sfromtheBinationalScienceFoundation(BSF),theIsraelScienceFoundation(ISF),andtheMinervaFoundation.1ElectronicColloquiumonComputationalComplexity,ReportNo.60(2006)ISSN1433-8092multilineararithmeticcircuits.WeproveanΩ(n4/3/log2n)lowerboundforthesizeofsyntacticallymultilineararithmeticcircuitscomputinganexplicitpolynomial.1.1SyntacticallyMultilinearArithmeticCircuitsAnarithmeticcircuitΦoverthefieldFandthesetofvariablesX={x1,...,xn}isadirectedacyclicgraphasfollows:EveryvertexvinΦiseitherofin-degree0orofin-degree2.EveryvertexvinΦofin-degree0islabelledbyeitheravariableinXorafieldelementinF.EveryvertexvinΦofin-degree2islabelledbyeither×or+.AnarithmeticcircuitΦiscalledanarithmeticformulaifΦisadirectedbinarytree(theedgesofanarithmeticformulaaredirectedfromtheleavestotheroot).LetΦbeanarithmeticcircuitoverthefieldFandthesetofvariablesX.TheverticesofΦarealsocalledgates.Everygateofin-degree0iscalledaninputgate.Everygateofin-degree2labelledby×iscalledaproductgate.Everygateofin-degree2labelledby+iscalledanadditiongate.Everygateofout-degree0iscalledanoutputgate.FortwogatesuandvinΦ,if(u,v)isanedgeinΦ,thenuiscalledasonofv,andviscalledafatherofu.ThesizeofΦ,denoted|Φ|,isthenumberofedgesinΦ.Sincethein-degreeofΦisatmost2,thesizeofΦisatmosttwicethenumberofgatesinΦ.ForagatevinΦ,defineΦvtobethesub-circuitofΦrootedatvasfollows:ThegatesofΦvareallthegatesuinΦsuchthatthereexistsadirectedpathfromutovinΦ.TheedgesandlabelsofΦvarethesameedgesandlabelsofΦ(restrictedtothesetofgatesofΦv).Anarithmeticcircuitcomputesapolynomialinanaturalway.ForagatevinΦ,definebΦv∈F[X]tobethepolynomialcomputedbyΦvasfollows:Ifvisaninputgatelabelledbyα∈F∪X,thenbΦv=α.Ifvisaproductgatewithsonsv1andv2,thenbΦv=bΦv1·bΦv2.Ifvisanadditiongatewithsonsv1andv2,thenbΦv=bΦv1+bΦv2.Forapolynomialf∈F[X],andagatevinΦ,wesaythatvcomputesfiff=bΦv.Forapolynomialf∈F[X],wesaythatΦcomputesfifthereexistsagateuinΦthatcomputesf.Apolynomialf∈F[X]iscalledmultilinearifthedegreeofeachvariableinfisatmostone.Anarith-meticcircuitΦiscalled(semantically)multilinearifeverygateinΦcomputesamultilinearpolynomial.AnarithmeticcircuitΦiscalledsyntacticallymultilinearifforeveryproductgatevinΦwithsonsv1andv2,thesetofvariablesthatoccurinΦv1andthesetofvariablesthatoccurinΦv2aredisjoint.1.2BackgroundandMotivationTherearetwowaystodefinemultilineararithmeticcircuits:asyntacticdefinition,andasemanticdefinition,asdescribedabove.Thesemanticdefinitionisanaturalone,butthesyntacticdefinitionis2moreconvenienttoworkwith.Note,forexample,thatgivenanarithmeticcircuitΦ,decidingwhetherΦissyntacticallymultilinearisstraightforward,whereasitisnotclearifonecandecidewhetherΦissemanticallymultilinearindeterministicpolynomialtime.Wenotealsothatsimilardistinctionbetweensemanticandsyntacticdefinitionsoccurinotherplacesincomputerscience(e.g.,readk-timesbranchingprograms).MultilineararithmeticcircuitsweredefinedbyNisanandWigdersonin[NW96].Themodelofsyntacti-callymultilineararithmeticformulaswasdefinedin[R04a].In[R04a],itisshownthatanymultilineararithmeticformulacomputingthedeterminant(orthepermanent)ofann×nmatrixmustbeofsizenΩ(logn).Priortoourwork,nolowerbounds(betterthantheΩ(nlogn)lowerboundofStrassen,andofBaurandStrassen)forthesizeofsyntacticallymultilineararithmeticcircuitswereknown.Thetechniquesof[R04a]forprovingsuper-polynomiallowerboundsforthesizeofmultilineararithmeticformulasfailforcircuits.Infact,[R04b]usedthesetechniquestoprovethatsyntacticallymultilineararithmeticcircuitsaresuper-polynomiallymorepowerfulthanmultilineararithmeticformulas.Morespecifically,thereexistsapolynomialfsuchthateverymultilineararithmeticformulacomputingfisofsizenΩ(logn),andonthe