Variable Partition Models

Eyal Kushilevitz, Noam NisanCambridge 1996 · DOI · OpenAlex

Abstract

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.
BibTeX
@inproceedings{kushilevitz1996variable,
  author = {Eyal Kushilevitz and Noam Nisan},
  title = {{Variable Partition Models}},
  booktitle = {Cambridge},
  year = {1996},
  doi = {10.1017/cbo9780511574948.008},
}

Loading related content...

Figure