Randomized Methods in Computation

《Randomized Methods in Computation》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、RandomizedMethodsinComputation:TentativeCollectionofReadingMaterialOdedGoldreichDepartmentofComputerScienceandAppliedMathematicsWeizmannInstituteofScience,Rehovot,Israel.July16,2011IcCopyright2011byOdedGoldreich.Permissiontomakecopiesofpartorallofthisworkforpersonalorclassroomuseis

2、grantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatnewcopiesbearthisnoticeandthefullcitationonthefirstpage.Abstractingwithcreditispermitted.IIPrefaceIwasadvisedtostarttheprefacewiththefollowingcoupleofpreliminaryremarks.Anoverviewofthemater

3、ialthatispresentedinthebodyofthistextfollows.TwoPreliminaryRemarksByRandomizedMethodsinComputationImeanthecollectionoftools,methods,andper-ceptionsthathaveanexplicitorimplicitrandomizedflavourandareusedintheanalysisofcomputation.Typically,butnotalways,thecomputationbeinganalyzedisra

4、ndomized,andinsuchcasestheuseofprobabilisticanalysisisexplicit.Nevertheless,thistextisnotacourseinprobabilitytheory;materialthatcanbelabeledasclassical“probabilitytheory”occupiesonlythefirstfive(orso)pagesofthefirstchapter(andmaterialthatcanbelabeled“probabilitytheory”appearsonlyinthe

5、firstchapter).1ThistentativecollectionofreadingmaterialregardingRandomizedMethodsinComputa-tionwascompiledbasedonextractstakenfromavarietyofsources.Someofthe“chapters”areextractsfrommybookoncomputationalcomplexity,whileothersreproducesurveysthatIwroteondifferentoccasionsandfordifferen

6、taudiences.Consequently,thiscollectionsuf-fersfromsomedrawbacks(whichalsooffersomeadvantages).Mostimportantly:•Somematerialappearsinmorethanoneofthe“chapters”(buttheperspectivesofferedareusuallydifferent).Furthermore,insomecasesthereareinconsistencies(between“chapters”)regardingtheexa

7、ctformulationsandnotation.•Some“chapters”putagreateremphasisontheresultsobtainedwhileothersputmoreemphasisonthetechniquesused.(ThismaybeOK;forcinguniformityheremaybeundesired.)•Theexpositionalstylevariesfromanovice-friendlystyleofatextbooktoalaconicstyleaimedatexperts.(Eventhismayh

8、aveabrightside:Itexposesth