Name
Abstract | ||
|---|---|---|
Alice and Bob are connected via a two-way binary channel. This paper describes an algorithm to enable Alice to send a message to Bob when 1) an oblivious adversary flips an unknown number of bits, $T$, on the channel; and 2) the message length $L$, and a desired error probability, $epsilon$ are public knowledge. With probability at least $1-epsilon$, our algorithm ensures that Bob receives the correct message, and that Alice and Bob terminate after sending a total of $L + O left( T + min left(T+1,frac{L}{log L} right) log left( frac{L}{epsilon} right) right)$ bits. When $epsilon = Omegaleft( frac{1}{poly(L)} right)$ and $T$ is large, the number of bits sent is $L + Oleft( T right)$, which is asymptotically optimal, assuming a conjecture by Haeupler. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Cryptography and Security | Alice and Bob,Theoretical computer science,Omega,Message length,Probability of error,Asymptotically optimal algorithm,Conjecture,Mathematics,Binary number |
DocType | Volume | Citations |
Journal | abs/1605.04486 | 0 |
PageRank | References | Authors |
0.34 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abhinav Aggarwal | 1 | 1 | 4.06 |
| Varsha Dani | 2 | 432 | 40.05 |
| Thomas P. Hayes | 3 | 659 | 54.21 |
| Jared Saia | 4 | 1019 | 96.95 |