On coherence, random-self-reducibility and self-co

ONCOHERENCE,RANDOM-SELF-REDUCIBILITY,ANDSELF-CORRECTIONJoanFeigenbaum,LanceFortnow,SophieLaplanteandAshishNaikAbstract.Westudythreetypesofself-reducibilitythataremotivatedbythetheoryofprogramverication.AsetAisrandom-self-reducibleifonecandeterminewhetheraninputxisinAbymakingrandomqueriestoanA-oracle.Thedistributionofeachquerymaydependonlyonthelengthofx.AsetBisself-correctableoveradistributionDifonecanconvertaprogramthatiscorrectonmostoftheprobabilitymassofDtoaprobabilisticprogramthatiscorrecteverywhere.AsetCiscoherentifonecandeterminewhetheraninputxisinCbyaskingquestionstoanoracleforCfxg.Werstshowthatadaptivecoherenceismorepowerfulthannon-adaptivecoherence,evenifthenonadaptivequerierisnonuniform.Blumetal.[Blum,LubyandRubinfeld,JournalofComputerandSystemSci-ences,59:549{595,1993]showedthateveryrandom-self-reduciblefunc-tionisself-correctable.Itisunknown,however,whetherself-correcta-bilityimpliesrandom-self-reducibility.Weshow,underthereasonablecomplexity-theoretichypothesisthatcertainhard,sparse,tallysetsex-ist,thatthereisaself-correctablefunctionthatisnotrandom-self-reducible.Foreasilysampleabledistributions,however,weshowthatconstructingaself-correctablefunctionthatisnotrandom-self-reducibleisashardasprovingthatPisdierentfromPP.Subjectclassications.68Q10.68Q15.68Q60.1.IntroductionConsiderafunctionfthatwewishtocomputebyaprobabilistic,polynomial-timeoracleTuringmachineMasfollows.Misallowedtoconsultthefunctionfasanoracleq(n)times,forsomepolynomialq,undertherestrictionthat,for2Feigenbaumetal.allinputstringsxandyoflengthn,forallstringsz,andforalli,1iq(n),theprobabilitythatzistheithquerythatMmakesoninputxisidenticaltotheprobabilitythatzistheithquerythatMmakesoninputy.Iffcanbecomputedinthismanner,thenitissaidtoberandom-self-reducible.Random-self-reduciblefunctionshavetheusefulpropertythat,eventhoughtheymaybehardtocomputedirectly,theycanbecomputedecientlyusingq(n)f-oracleswithoutrevealingtheirinputtotheoracles.Inadditiontotheirapplicationtocryptography,thesefunctionshavebeenusedextensivelyinareassuchasaverage-casecomplexity,lowerbounds,programchecking,testing,andcorrect-ing,andprobabilisticallycheckableproofs.Forreferencesandexplanationsoftheseapplications,seeFeigenbaum(1993).Yao(1990)denedthenotionofcoherence,whichistheweakestformofprobabilisticself-reducibility.Afunctionfiscoherentifthereexistsaproba-bilisticpolynomial-timeoracleTuringmachinecalledtheexaminerthatcom-putesfusingfasanoraclewithoutqueryingtheinput.Buhrmanetal.(1995)usedthepropertyofdeterministiccoherence(calledautoreducibility)asatooltoseparatecomplexityclasses.Itisknownthatallnonadaptivelyrandom-self-reduciblefunctionsarenonadaptivelycoherentwithpolynomial-sizedad-vice(Beigel&Feigenbaum1992).Despitenotableprogressinourunderstandingofthesetopics(seeBeigel&Feigenbaum1992,Feigenbaum&Fortnow1993,Feigenbaumetal.1994,Buhrmanetal.1995),manycomplexity-theoreticquestionsaboutrandom-self-reducibilityandcoherenceremainopen.Thispaperexaminestwoofthem.Werstaddressthepowerofadaptivenessandadviceincoherence.Feigenbaumetal.(1994)showedthatthereisarandom-self-reduciblefunctionfthatisnotnonadaptivelyrandom-self-reducible.However,thefunctionftheyexhibitedcanbecomputedinpolynomialtimeiftheTuringmachineisprovidedwithpolynomial-sizedadviceasanauxiliaryinput(Karp&Lipton1980).Indeed,allknownresultsthatseparateadaptivefromnonadaptiveself-reductions(seeHemaspaandraetal.1996,Feigenbaumetal.1994)dosousingfunctionscom-putableinpolynomialtimewithadvice.Weshowthatadaptiveexaminersaremorepowerfulthannonadaptiveex-aminers,evenifthenonadaptiveonesusepolynomialadvice.Theorem:Thereexistsacoherentfunctionthatisnotnonadap-tivelycoherent,evenwithpolynomialadvice.Next,westudytherelationshipbetweenrandom-self-reducibilityandself-correctability.Blumetal.(1993)denedprogramself-correctioninordertoaddressthefollowingquestion.LetPbeaprogramforwhichonecandetermineCoherence,RSRandSelf-correction3thatthenumberofinputsonwhichPerrs,whilenotnecessarilyzero,islimited.IsitpossibletowriteanauxiliaryprogramCthatcorrectsP’serrorswithhighprobability?Moreprecisely,onanyinput,Cshouldproducethecorrectanswerwithhighprobability,andCmaycallthe(potentiallyfaulty)programPseveraltimesinthecourseofitscomputation.Blum,Luby,andRubinfeldobservedthateveryrandom-self-reduciblefunc-tionisalsoself-correctable.Moreover,allknownself-correctingschemesusesomeformofrandom-self-reducibility.Thisimmediatelyraisesthequestionofwhetherthetwonotionsareequivalent,i.e.,whethereveryself-correctablefunctionisrandom-self-reducible.Ourrstresultgivesaconditionalnegativeanswertothisquestion.Theorem:IfUEEEXP6REEEXP,thenthereexistsafunc-tionfthatisnonadaptivelyself-correctablebutnotnonadaptivelyrandom-self-reducible.AlthoughthecomplexityclassesUEEEXPandREEEXPmayappearob-scure,wenotethatthehypothesisUEEEXP6REEEXPisonlyusedtoconstructasucientlysparsetallylanguageinUPRP.Theexistenceofarbitrarilysparseintractablelanguagesisoftenputforthasareasonablecomplexityhypothesis(seeBeigeletal.1991,Beigel&Feigenbaum1992,Feigenbaumetal.1994,