The Communication Complexity of Relations

Eyal Kushilevitz, Noam NisanCambridge 1996 · DOI · OpenAlex

Abstract

In the first part of this book we were interested in computing functions. That is, for any input (x, y) there was a unique value f(x, y) that Alice and Bob had to compute. More general types of problems are relations. In this case, on input (x, y) there might be several values that are valid outputs. Formally,
BibTeX
@inproceedings{kushilevitz1996communication,
  author = {Eyal Kushilevitz and Noam Nisan},
  title = {{The Communication Complexity of Relations}},
  booktitle = {Cambridge},
  year = {1996},
  doi = {10.1017/cbo9780511574948.006},
}

Loading related content...

Figure