Communication Complexity of Key Agreement on Small Ranges

Jin-yi Cai, Richard J. Lipton, Luc Longpré, Mitsunori Ogihara, Kenneth W. Regan, D. SivakumarSTACS 1995 · OpenReview

Abstract

We study a variation on classical key-agreement and consensus problems in which the key space S is the range of a random variable that can be sampled. We give tight upper and lower bounds of [log2 k] bits on the communication complexity of agreement on some key in S, using a form of Sperner's Lemma, and give bounds on other problems. In the case where keys are generated by a probabilistic polynomial-time Turing machine, we show agreement possible with zero communication if every fully polynomial-time approximation scheme (fpras) has a certain symmetry-breaking property.
BibTeX
@inproceedings{cai1995communication,
  author = {Jin-yi Cai and Richard J. Lipton and Luc Longpré and Mitsunori Ogihara and Kenneth W. Regan and D. Sivakumar},
  title = {{Communication Complexity of Key Agreement on Small Ranges}},
  booktitle = {STACS},
  year = {1995},
  url = {https://openreview.net/forum?id=CYZfLXebcLQ},
}

Loading related content...

Figure