## Communication Complexity and Parallel ComputingThe 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 |

317 | |

331 | |

### Other editions - View all

### Common terms and phrases

1-fooling set algorithms area complexity Bal(X balanced partition bits Boolean circuit computing Boolean function Boolean variables branching programs Chomsky hierarchy communication protocols complexity measures complexity of f computing f computing problem consider construct contains corresponding crossing sequence decision trees defined Definition denote deterministic directed graph edge-separator edges Exercise exists finite fooling set function f grid-graph Hromkovic input assignment input processors input variables layout left computer Lemma Let f Let G linear log2 lower bound method lower bound proof monotone Boolean Monte Carlo nodes nondeterministic communication complexity nondeterministic protocol observe Obviously one-way communication complexity output variables parallel computing partition 77 planar graph plexity polylogarithmic positive integer proof of Theorem protocol computing proving lower bounds random register machines regular language rows s-communication second computer Section sequence set of input submatrix Turing machines vertex-cut vertex-separator VLSI circuits VLSI program

### 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.

### References to this book

Complexity Theory: Exploring the Limits of Efficient Algorithms Ingo Wegener No preview available - 2005 |