通信復雜性與并行計算（影印版）

1Introduction
1.1MotivationandAims
1.2ConceptandOrganization
1.3HowtoReadtheBook
2CommunicationProtocolModels
2.1BasicNotions
2.1.1Introduction
2.1.2Alphabets,Words,andLanguages
2.1.3BooleanFunctionsandBooleanMatrices
2.1.4RepresentationofComputingProblems
2.1.5Exercises
2.2CommunicationComplexityAccordingtoaFixedPartition
2.2.1Definitions
2.2.2MethodsforProvingLowerBounds
2.2.3TheoreticalPropertiesofCommunicationComplexityAccordingtoaFixedPartition
2.2.4Exercises
2.2.5ResearchProblems
2.3CommunicationComplexity
2.3.1Introduction
2.3.2Definitions
2.3.3LowerBoundMethods
2.3.4TheoreticalPropertiesofCommunicationComplexity
2.3.5CommunicationComplexityandChomskyHierarchy
2.3.6Exercises
2.3.7ResearchProblems
2.4One-WayCommunicationComplexity
2.4.1Introduction
2.4.2Definitions
2.4.3MethodsforProvingLowerBounds
2.4.4CommunicationComplexityVersusOne-wayCommunicationComplexity
2.4.5Exercises
2.4.6ResearchProblems
2.5NondeterministicCommunicationComplexityandRandomizedProtocols
2.5.1Introduction
2.5.2NondeterministicProtocols
2.5.3LowerBoundsonNondeterministicCommunicationComplexity
2.5.4DeterministicProtocolsVersusNondeterministicProtocols
2.5.5RandomizedProtocols
2.5.6RandomnessVersusNondeterminismandDeterminism
2.5.7Exercises
2.5.8Researchproblems
2.6AnImprovedModelofCommunicationProtocols
2.6.1Introduction
2.6.2Definitions
2.6.3LowerBoundMethods
2.6.4CommunicationComplexityVersuss-communicationComplexity
2.6.5SomePropertiesofs-communicationComplexity
2.6.6Exercises
2.6.7Problems
2.7BibliographicalRemarks
3BooleanCircuits
3.1Introduction
3.2DefinitionsandFundamentalProperties
3.2.1Introduction
3.2.2BooleanCircuitModels
3.2.3FundamentalObservations
3.2.4Exercises
3.3LowerBoundsontheAreaofBooleanCircuits
3.3.1Introduction
3.3.2Definitions
3.3.3LowerBoundsontheAreaComplexityMeasures
3.3.4AComparisonoftwoAreaComplexityMeasures
3.3.5Three-DimensionalLayout
3.3.6Exercises
3.3.7Problems
3.4TopologyofCircuitsandLowerBounds
3.4.1Introduction
3.4.2Separators
3.4.3LowerBoundsonBooleanCircuitswithaSublinearSeparator
3.4.4CircuitStructuresforWhichCommunicationComplexityDoesNotHelp
3.4.5PlanarBooleanCircuits
3.4.6Exercises
3.4.7Problems
3.5LowerBoundsontheSizeofUnboundedFan-inCircuits
3.5.1Introduction
3.5.2MethodofCommunicationComplexityofInfiniteBases
3.5.3UnboundedFan-inCircuitswithSublinearVertex-Separators
3.5.4Exercises
3.5.5Problems
3.6LowerBoundsontheDepthofBooleanCircuits
3.6.1Introduction
3.6.2MonotoneBooleanCircuits
3.6.3CommunicationComplexityofRelations
3.6.4CharacterizationsofCircuitDepthbytheCommunicationComplexityofRelations
3.6.5Exercises
3.6.6ResearchProblems
3.7BibliographicalRemarks
4VLSICircuitsandInterconnectionNetworks
4.1Introduction
4.2Definitions
4.2.1Introduction
4.2.2AVLSIcircuitModel
4.2.3ComplexityMeasures
4.2.4ProbabilisticModels
4.2.5Exercises
4.3LowerBoundsonVLSIComplexityMeasures
4.3.1Introduction
4.3.2LowerBoundsonAreaComplexity
4.3.3LowerBoundsonTradeoffsofAreaandTime
4.3.4VLSIcircuitswithSpecialCommunicationStructures
4.3.5Exercises
4.3.6Problems
4.4InterconnectionNetworks
4.4.1Introduction
4.4.2AModelofInterconnectionNetworks
4.4.3SeparatorsaridLowerBounds
4.4.4Exercises
4.4.5Problems
4.5MultilectiveVLSIcircuits
4.5.1IntroductionandDefinitions
4.5.2MultilectivityVersusSemilectivity
4.5.3LowerBoundsonMultilectiveVLSIprograms
4.5.4Exercises
4.5.5Problems
4.6BibliographicalRemarks
5SequentialComputations
5.1Introduction
5.2FiniteAutomata
5.2.1Introduction
5.2.2Definitions
5.2.3One-WayCommunicationComplexityandLowerBoundsontheSizeofFiniteAutomata
5.2.4UniformProtocols
5.2.5Exercises
5.2.6ResearchProblems
5.3TuringMachines
5.3.1Introduction
5.3.2TimeComplexityofClassicalTuringMachines
5.3.3SequentialSpaceandTime-SpaceComplexity
5.3.4Exercises
5.3.5ResearchProblems
5.4DecisionTreesandBranchingPrograms
5.4.1Introduction
5.4.2Definitions
5.4.3CapacityofBranchingPrograms
5.4.4LowerBoundsontheDepthofDecisionTrees
5.4.5Exercises
5.4.6ResearchProblems
5.5BibliographicalRemarks
References
Index