Skip to main navigation Skip to search Skip to main content

Communication complexity of key agreement on small ranges

  • Jin Yi Cai
  • , Richard J. Lipton
  • , Luc Longpré
  • , Mitsunori Ogihara
  • , Kenneth W. Regan
  • , D. Sivakumar
  • SUNY Buffalo
  • Princeton University
  • University of Texas at El Paso
  • University of Rochester

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

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’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.

Original languageEnglish
Title of host publicationSTACS 1995 - 12th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
EditorsErnst W. Mayr, Claude Puech
PublisherSpringer Verlag
Pages38-49
Number of pages12
ISBN (Print)3540590420, 9783540590422
DOIs
StatePublished - 1995
Event12th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1995 - Munich, Germany
Duration: Mar 2 1995 → Mar 4 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume900

Conference

Conference12th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1995
Country/TerritoryGermany
CityMunich
Period03/2/95 → 03/4/95

Fingerprint

Dive into the research topics of 'Communication complexity of key agreement on small ranges'. Together they form a unique fingerprint.

Cite this