We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
Published online by Cambridge University Press: 05 November 2009
This book surveys the mathematical field of communication complexity. whereas the original motivation for studying this issue comes from computer systems and the operations they perform, the underlying issues can be neatly abstracted mathematically. This is the approach taken here.
Communication
The need for communication arises whenever two or more computers, components, systems, or humans (in general, “parties”) need to jointly perform a task that none of them can perform alone. This may arise, for example, due to the lack of resources of any single party or due to the lack of data available to any single party.
In many cases, the need for communication is explicit: When we search files on a remote computer it is clear that the requests and answers are actually communicated (via electrical wires, optical cables, radio signals, etc.). In other cases, the communication taking place is more implicit: When a single computer runs a program there is some communication between the different parts of the computer, for example, between the CPU and the memory, or even among different parts of the CPU. In yet other cases, there is no real communication going on but it is still a useful abstraction. For a problem whose solution relies on several pieces of data, we can imagine that these pieces of data need to communicate with each other in order to solve the problem; in reality, of course, this communication will be achieved by a processor accessing them all.
Complexity
The notion of complexity is becoming more and more central in many branches of science and in particular in the study of various types of computation.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.
