资源描述：
《Communication complexity book.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、CommunicationComplexitqManyaspectsoftheinternalandexternalworkingsofcomputerscanbeviewed,atdifferentlevels,asaseriesofcommunicationprocesses.Communicationcomplexityisthemathematicaltheoryofsuchcommunicationprocesses.Itisalsooftenusedasanabstractmodelof
2、otheraspectsofcomputation.ItextendsShannon'sinformationtheory,allowingtwowaycommunicationandarbitraryprocesses.Thisbooksurveysthismathematicaltheory,concentratingonthequestionofhowmuchcommunicationisnecessaryforanyparticularprocess.Thefirstpartoftheboo
3、kisdevotedtothesimpletwo-partymodelintroducedbyYaoin1979,whichisstillthemostwidelystudiedmodel.Thesecondparttreatsnewermodels,suchasvariablepartitionmodels,communicationcomplexityofrelations,andmultipartyprotocols,developedtodealwithmorecomplicatedcomm
4、unicationprocesses.Finally,applicationsofthesemodels,includingTuringmachines,booleancircuits,computernetworks,VLSIcircuits,pseudorandomness,anddatastructures,aretreatedinthethirdpartofthebook.Inparticular,communicationargumentsareusedtoprovelowerbounds
5、formanyproblemsarisingintheseareas.Thisisanessentialresourceforgraduatestudentsandresearchersintheoreticalcomputerscience,circuits,networks,VLSI,andinformationtheory.CommunicationComplexityCommunicationComplexityEyalKushilevitzNoamNisanTechnion-IsraelH
6、ebrewUniversity,InstituteofTechnology,JerusalemHaifa.....CAMBRIDGEUNIVERSITYPRESSCAMBRIDGEUNIVERSITYPRESSCambridge,NewYork,Melbourne,Madrid,CapeTown,Singapore,SaoPauloCambridgeUniversityPressTheEdinburghBuilding,CambridgeCB22RU,UKPublishedintheUnitedSt
7、atesofAmericabyCambridgeUniversityPress,NewYorkwww.cambridge.orgInformationonthistitle:www.cambridge.org/9780521560672©CambridgeUniversityPress1997Thispublicationisincopyright.Subjecttostatutoryexceptionandtotheprovisionsofrelevantcollectivelicensingag
8、reements,noreproductionofanypartmaytakeplacewithoutthewrittenpermissionofCambridgeUniversityPress.Firstpublished1997Thisdigitallyprintedfirstpaperbackversion2006AcataloguerecordforthispublicationisavailablefromtheBritishLibraryLibraryof
