Reischuk Average Case Complexity of Unbounded Fani

AverageCaseComplexityofUnboundedFaninCircuitsAndreasJakoby1;2andRudigerReischuk21DepartmentofComputerScience,UniversityofToronto2InstitutfurTheoretischeInformatik,Med.UniversitatzuLubeckJanuary2000AbstractSeveralauthorshaveshownthatthePARITY-functioncannotbecomputedbyunboundedfanincircuitsofsmalldepthandpolynomialsize.Evenmore,constantdepthkcircuitsofsizeexp(n(1=k))givewrongresultsforPARITYforalmosthalfofallinputs.Wegeneralizetheseresultsintwodirections.First,weobtainsimilartightlowerboundsfortheaveragecasecomplexityofcircuits,measuringthecomputationaldelayinsteadofthestaticcircuitdepth.Secondly,withrespecttoaveragedelayofunboundedfanincircuitswecompletelyclassifyallparallelprexfunctions,forwhichPARITYisjustonepromimentexample.Itisshownthatonlytwocasescanoccur:aparallelprexfunctionsfeitherhasthesameaveragecomplexityasPARITY,thatistheaveragedelayhastobeoforder(logn=loglogs)forcircuitsofsizes,orfcanbecomputedwithconstantaveragedelayandalmostlinearsize{thereisnocomplexitylevelinbetween.Thisclassicationisachievedbyanalyzingthealgebraicstructureofsemigroupsthatcorrespondtoparallelprexfunctions.ItextendsmethodsdevelopedforboundedfanincircuitsbytherstauthorinhisPh.D.Thesis.1IntroductionToanalysetheaverage-casecomplexityofBooleanfunctionsadynamiccomplexitymeasureforBooleancircuitsbasedonthenotionofdelayhasbeenintroducedin[JRS94].FortheclassicalcircuitmodelwithOR,ANDandNOTgatesofboundedfaninandfanoutwehaveshownthatn-aryfunctionsliketheOR,theadditionorthresholdfunctionswithaxedthresholdcanbecomputedmuchfasterontheaveragecomparedtotheworst-caseforwhichthetriviallogndepthlowerboundholds.OtherfunctionslikePARITYdonotallowasignicantspeedupoftheaveragetimecomplexity,regardlessofthesizeofthecircuits.In[JRSW94]wehavegeneralizedourinvestigationstocomputingarbitraryprexfunctions.Tightboundsfortheaveragecomplexityhavebeenobtainedbyanalysingthealgebraicstructureofthesemigroupsthatcorrespondtotheprexoperator.Theseresultshavebeenextendedin[Jak98,Jak99]toparallelprexcomputationsinothermodelslikelineararraysandnetworksofautomata.AdierentlineofresearchhasconsideredthecomplexityofBooleanfunctionsinacircuitmodelwheregatesofarbitrarylargefanincanbeused.ItiswellknownthatinthismodeleveryBooleanfunctioncanbecomputedinconstantdepthbycircuitsofexponentialsize.FunctionsliketheORortheadditionagaincanbecomputedmuchmoreecient,thatisinconstantdepthandpolynomialsize[ChFL83a].ButPARITYremainsdicult{thebestspeedupforpolynomialsizeonecanobtainisdepth(logn=loglogn)[Yao85].Hastadhasprovenoptimallowersizeboundswithrespecttothecircuitdepthbyapplyingtheprobabilisticrestrictionmethodveryprecisely.BabaiandCaihaveshownthatcircuitsofconstantdepthkandsizeexp(n(1=k))generatewrongresultsforPARITYforalmosthalfofallinputs[Bab87,Cai89].SmolenskyhaspresentedanalgebraicapproachtogeneralizethePARITYlowerboundtoarbitrarymodm-functions.InthispaperwecombinebothquestionsandinvestigatewhetherPARITYcanbecomputedmoreecientlybyunboundedfanincircuitsontheaverage.Thatmeans,insteadofthestaticcomplexitymeasuredepthweconsiderthedynamicmeasuredelay.Krapchenkohasgivenanexampleshowingthatanincreaseofthecircuitsizecannotbeavoidedingeneralwhenadelayminimalcircuitistransformedintoacircuitofminimaldepth[Kra78].Thus,lowerboundsoncircuitdepth,eventheonesin[Bab87,Cai89]foralmosthalfofallinputs,donotdirectlytranslateintoboundsfortheaveragedelay.AtthesametimewetrytoclassifyBooleanfunctionsaccordingtotheiraveragecasecomplexityintheunboundedfaninmodel.Ourworkstartsbyinvestigatingalgebraicpropertiesofthecorrespondingsemigroupsinasimilarspiritasin[JRSW94,Jak98]nowtailoredtounboundedfanincomputations.1VersionJanuary20002Fortheworst-casecomplexityChandra,FortuneandLiptonhaveinvestigatedthealgebraicstructureofprexoperatorsandshownthatconstantdepthandpolynomialsizecannotbeachievedsimultaneouslyifthesemigroupcontainsasubgroup[ChFL83a].Theseresultscannotsimplybetranslatedtotheaveragecasebecausetheydonotholdunderthissetting.ConsiderthefollowingsimpleexampleofanextensionofthePARITYoperator,whichstillcontainsthe2-elementgroupasasubgroup.Letuscallthisfunctionparitywithreset,:f0;1;rg!f0;1g,denedby(w):=0ifw=orw[jwj]=r;((w[1;jwj1]);w[jwj])else.Aninputvaluerresetsthevalueofthecurrentprexto0.SinceacircuitthatcomputestheparitywithresetfunctioncanalsobeusedtocomputePARITY,thefunctioncannotbecomputedbyapolynomialsizecircuitwithdeptho(logn=loglogn).Ontheotherhand,ourresultsimplythatcanbecomputedbyacircuitofnearlylinearsizewithinaconstantaveragedelay.Similarly,theclassicationofBilardi,Preparataforconstantdepthandlinearsizeprexcircuitsbasedonthenotionofmonoidelcycles[BiPr90]doesnotextendtotheaveragecase.Thesecondmajorstepinouranalysisoftheproblemisanontrivialextensionoftheprobabilisticrestrictionmethodtoarbitrarynitedomains.Thisway,wecandeduceboundsontheerrorprobabilitiesofaverage-casedelayboundedcircuitswithunboundedfaningates,fromwhichthelowerboundsforprexfunctionsofcertaintypeswillfollow.Theresultsareasfollows.Forparityandotherprexfunctionswithagrouplikestructure\embedde