Name
Abstract | ||
|---|---|---|
Abstract This paper studies a variation on classical key-agreement and consensus problems in which the set S of possible keys is the range of a random variable that can be sampled. We give tight upper and lower bounds ofdlog2ke 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, agreement is shown to be possible with zero communication if every fully polynomial-time approximation scheme (fpras) has a certain symmetry-breaking property. Topics Computational complexity, cryptography. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1007/3-540-59042-0_60 | STACS |
Keywords | Field | DocType |
turing machine,consensus problem,random variable,symmetry breaking,fully polynomial time approximation scheme,communication complexity,upper and lower bounds,polynomial time,computational complexity | 2-EXPTIME,Quantum complexity theory,Complexity class,Discrete mathematics,Average-case complexity,Combinatorics,PSPACE,UP,Alternating Turing machine,Mathematics,NP | Conference |
Citations | PageRank | References |
1 | 0.37 | 32 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jin-Yi Cai | 1 | 2327 | 239.71 |
| Richard J. Lipton | 2 | 6412 | 1796.57 |
| Luc Longpré | 3 | 245 | 30.26 |
| Mitsunori Ogihara | 4 | 3135 | 257.04 |
| Kenneth W. Regan | 5 | 201 | 23.15 |
| D. Sivakumar | 6 | 3515 | 389.02 |
| nsf grants ccr | 7 | 1 | 0.37 |