Communication Complexity of Key Agreement on Small Ranges
Lists
Only you see this
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...