@inproceedings{d53da61b260f43d8b79bd2ae068ff90a,
title = "Communication complexity of key agreement on small ranges",
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 [log2k] bits on the communication complexity of agreement on some key in S, using a form of Sperner{\textquoteright}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.",
author = "Cai, \{Jin Yi\} and Lipton, \{Richard J.\} and Luc Longpr{\'e} and Mitsunori Ogihara and Regan, \{Kenneth W.\} and D. Sivakumar",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1995.; 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1995 ; Conference date: 02-03-1995 Through 04-03-1995",
year = "1995",
doi = "10.1007/3-540-59042-0\_60",
language = "English",
isbn = "3540590420",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "38--49",
editor = "Mayr, \{Ernst W.\} and Claude Puech",
booktitle = "STACS 1995 - 12th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",
address = "Germany",
}