Communication Complexity and Parallel Computing

Front Cover
Springer Science & Business Media, Feb 26, 1997 - Computers - 336 pages
0 Reviews
The communication complexity of two-party protocols is an only 15 years old complexity measure, but it is already considered to be one of the fundamen tal complexity measures of recent complexity theory. Similarly to Kolmogorov complexity in the theory of sequential computations, communication complex ity is used as a method for the study of the complexity of concrete computing problems in parallel information processing. Especially, it is applied to prove lower bounds that say what computer resources (time, hardware, memory size) are necessary to compute the given task. Besides the estimation of the compu tational difficulty of computing problems the proved lower bounds are useful for proving the optimality of algorithms that are already designed. In some cases the knowledge about the communication complexity of a given problem may be even helpful in searching for efficient algorithms to this problem. The study of communication complexity becomes a well-defined indepen dent area of complexity theory. In addition to a strong relation to several funda mental complexity measures (and so to several fundamental problems of com plexity theory) communication complexity has contributed to the study and to the understanding of the nature of determinism, nondeterminism, and random ness in algorithmics. There already exists a non-trivial mathematical machinery to handle the communication complexity of concrete computing problems, which gives a hope that the approach based on communication complexity will be in strumental in the study of several central open problems of recent complexity theory.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

1 Introduction
1
12 Concept and Organization
4
13 How to Read the Book
6
2 Communication Protocol Models
7
213 Boolean Functions and Boolean Matrices
11
214 Representation of Computing Problems
16
215 Exercises
20
22 Communication Complexity According to a Fixed Partition
23
343 Lower Bounds on Boolean Circuits with a Sublinear Separator
192
344 Circuit Structures for Which Communication Complexity Does Not Help
196
345 Planar Boolean Circuits
200
346 Exercises
215
347 Problems
217
352 Method of Communication Complexity of Infinite Bases
218
353 Unbounded Fanin Circuits with Sublinear VertexSeparators
222
354 Exercises
224

222 Methods for Proving Lower Bounds
30
223 Theoretical Properties of Communication Complexity According to a Fixed Partition
53
224 Exercises
57
225 Research Problems
59
23 Communication Complexity
60
232 Definitions
61
233 Lower Bound Methods
62
234 Theoretical Properties of Communication Complexity
70
235 Communication Complexity and Chomsky Hierarchy
77
236 Exercises
82
237 Research Problems
83
242 Definitions
84
243 Methods for Proving Lower Bounds
86
244 Communication Complexity Versus Oneway Communication Complexity
92
245 Exercises
95
246 Research Problems
96
25 Nondeterministic Communication Complexity and Randomized Protocols
97
252 Nondeterministic Protocols
98
253 Lower Bounds on Nondeterministic Communication Complexity
105
254 Deterministic Protocols Versus Nondeterministic Protocols
109
255 Randomized Protocols
115
256 Randomness Versus Nondeterminism and Determinism
123
257 Exercises
127
258 Research problems
130
26 An Improved Model of Communication Protocols
131
262 Definitions
132
263 Lower Bound Methods
135
264 Communication Complexity Versus scommunication Complexity
139
265 Some Properties of scommunication Complexity
140
266 Exercises
143
267 Problems
144
3 Boolean Circuits
151
32 Definitions and Fundamental Properties
152
323 Fundamental Observations
159
324 Exercises
163
33 Lower Bounds on the Area of Boolean Circuits
164
333 Lower Bounds on the Area Complexity Measures
167
334 A Comparison of two Area Complexity Measures
173
335 ThreeDimensional Layout
179
336 Exercises
182
337 Problems
184
34 Topology of Circuits and Lower Bounds
185
355 Problems
225
362 Monotone Boolean Circuits
226
363 Communication Complexity of Relations
229
364 Characterizations of Circuit Depth by the Communication Complexity of Relations
231
365 Exercises
236
366 Research Problems
237
4 VLSI Circuits and Interconnection Networks
241
42 Definitions
242
423 Complexity Measures
247
424 Probabilistic Models
250
425 Exercises
251
43 Lower Bounds on VLSI Complexity Measures
252
433 Lower Bounds on Tradeoffs of Area and Time
254
434 VLSI circuits with Special Communication Structures
258
435 Exercises
263
436 Problems
264
442 A Model of Interconnection Networks
265
443 Separators and Lower Bounds
266
444 Exercises
270
452 Multilectivity Versus Semilectivity
271
453 Lower Bounds on Multilective VLSI programs
272
454 Exercises
279
455 Problems
280
5 Sequential Computations
283
52 Finite Automata
284
522 Definitions
285
523 OneWay Communication Complexity and Lower Bounds on the Size of Finite Automata
287
524 Uniform Protocols
288
525 Exercises
294
526 Research Problems
295
532 Time Complexity of Classical Turing Machines
296
533 Sequential Space and TimeSpace Complexity
299
534 Exercises
301
535 Research Problems
302
542 Definitions
303
543 Capacity of Branching Programs
306
544 Lower Bounds on the Depth of Decision Trees
309
545 Exercises
310
546 Research Problems
311
References
317
Index
331
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 323 - M. Karchmer, R. Raz, A. Wigderson, "On Proving Super-Logarithmic Depth Lower Bounds via the Direct Sum in Communication Complexity", Structures in Complexity Theory '91, pp.
Page 327 - Razborov: Lower bounds for the monotone complexity of some Boolean functions. Dokl. Akad. Nauk SSSR 281 (1985), 798-801 (in Russian). English translation: Soviet Math.
Page 328 - Applications of matrix methods for the theory of lower bounds in computational complexity", Combinatorica 10 pp.
Page 327 - WJ Paul. A 2.5n-lower bound on the combinational complexity of Boolean functions. SIAM J. comput. 6.

References to this book

Komplexitatstheorie
Ingo Wegener
No preview available - 2003
All Book Search results »