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
In the standard two-party model the input (x, y) is partitioned in a fixed way. That is, Alice always gets x and Bob always gets y. In this chapter we discuss models in which the partition of the input among the players is not fixed. The main motivation for these models is that in many cases we wish to use communication complexity lower bounds to obtain lower bounds in other models of computation. This would typically require finding a communication complexity problem “hidden” somewhere in the computation that the model under consideration must perform. Because in such a model the input usually is not partitioned into two distinct sets x1, …, xn and y1, …, yn, such a partition must be given by the reduction. In some cases the partition can be figured out and fixed. In some other cases we must use arguments regarding any partition (of a certain kind). That is, we require a model where the partition is not fixed beforehand but the protocol determines the partition (independently of the particular input). Several such “variable partition models” are discussed in this chapter.
Throughout this chapter the input will be m Boolean variables x1, …, xm, and we consider functions f: {0, l}m → {0, 1}. We will talk about the communication complexity of f between two disjoint sets of variables S and T. That is, one player gets all bits in S and the other all bits in T
Worst-Case Partition
The simplest variable partition model we may consider is the “worst-case” partition: split the input into two sets in the way that maximizes the communication complexity.
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.
