通信复杂性与并行计算.（影印版）

.2.3.3 lower bound methods
2.3.4 theoretical properties of communication complexity
2.3.5 communication complexity and chomsky hierarchy
2.3.6 exercises
2.3.7 research problems
2.4 one-way communication complexity
2.4.1 introduction
2.4.2 definitions
2.4.3 methods for proving lower bounds
2.4.4 communication complexity versus one-way communication complexity
2.4.5 exercises
2.4.6 research problems
2.5 nondeterministic communication complexity and randomized protocols
2.5.1 introduction
2.5.2 nondeterministic protocols
2.5.3 lower bounds on nondeterministic communication complexity
2.5.4 deterministic protocols versus nondeterministic protocols
2.5.5 randomized protocols
2.5.6 randomness versus nondeterminism and determinism
2.5.7 exercises
2.5.8 research problems
2.6 an improved model of communication protocols
2.6.1 introduction
2.6.2 definitions
2.6.3 lower bound methods
2.6.4 communication complexity versus s-communication complexity
2.6.5 some properties of s-communication complexity
2.6.6 exercises
2.6.7 problems
2.7 bibliographical remarks
3 boolean circuits
3.1 introduction
3.2 definitions and fundamental properties
3.2.1 introduction
3.2.2 boolean circuit models
3.2.3 fundamental observations
3.2.4 exercises
3.3 lower bounds on the area of boolean circuits
3.3.1 introduction
3.3.2 definitions
3.3.3 lower bounds on the area complexity measures
3.3.4 a comparison of two area complexity measures
3.3.5 three-dimensional layout
3.3.6 exercises
3.3.7 problems
3.4 topology of circuits and lower bounds
3.4.1 introduction
3.4.2 separators
3.4.3 lower bounds on boolean circuits with a sublinear separator
3.4.4 circuit structures for which communication complexity does not help
3.4.5 planar boolean circuits
3.4.6 exercises
3.4.7 problems
3.5 lower bounds on the size of unbounded fan-in circuits
3.5.1 introduction
3.5.2 method of communication complexity of infinite bases
3.5.3 unbounded fan-in circuits with sublinear vertex-separators
3.5.4 exercises
3.5.5 problems
3.6 lower bounds on the depth of boolean circuits
3.6.1 introduction
3.6.2 monotone boolean circuits
3.6.3 communication complexity of relations
3.6.4 characterizations of circuit depth by the communication complexity of relations
3.6.5 exercises
3.6.6 research problems
3.7 bibliographical remarks
4 vlsi circuits and interconnection networks
4.1 introduction
4.2 definitions
4.2.1 introduction
4.2.2 a vlsi circuit model
4.2.3 complexity measures
4.2.4 probabilistic models
4.2.5 exercises
4.3 lower bounds on vlsi complexity measures
4.3.1 introduction
4.3.2 lower bounds on area complexity
4.3.3 lower bounds on tradeoffs of area and time
4.3.4 vlsi circuits with special communication structures
4.3.5 exercises
4.3.6 problems
4.4 interconnection networks
4.4.1 introduction
4.4.2 a model of interconnection networks
4.4.3 separators arid lower bounds
4.4.4 exercises
4.4.5 problems
4.5 multilective vlsi circuits
4.5.1 introduction and definitions
4.5.2 multilectivity versus semilectivity
4.5.3 lower bounds on multilective vlsi programs
4.5.4 exercises
4.5.5 problems
4.6 bibliographical remarks
5 sequential computations
5.1 introduction
5.2 finite automata
5.2.1 introduction
5.2.2 definitions
5.2.3 one-way communication complexity and lower bounds on the size of finite automata
5.2.4 uniform protocols
5.2.5 exercises
5.2.6 research problems
5.3 turing machines
5.3.1 introduction
5.3.2 time complexity of classical turing machines
5.3.3 sequential space and time-space complexity
5.3.4 exercises
5.3.5 research problems
5.4 decision trees and branching programs
5.4.1 introduction
5.4.2 definitions
5.4.3 capacity of branching programs
5.4.4 lower bounds on the depth of decision trees
5.4.5 exercises
5.4.6 research problems
5.5 bibliographical remarks
references
index