The Communication Complexity of Relations
Lists
Only you see this
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...