Binary Causal-Adversary Channels
| dc.creator | Langberg, Michael | |
| dc.creator | Jaggi, Sidharth | |
| dc.creator | Dey, Bikash Kumar | |
| dc.date | 2009-01-13 | |
| dc.date | 2009-01-28 | |
| dc.date.accessioned | 2026-07-07T12:34:45Z | |
| dc.date.available | 2026-07-07T12:34:45Z | |
| dc.description | In this work we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x=(x_1,...,x_n) bit-by-bit over a communication channel. The adversarial jammer can view the transmitted bits x_i one at a time, and can change up to a p-fraction of them. However, the decisions of the jammer must be made in an online or causal manner. Namely, for each bit x_i the jammer's decision on whether to corrupt it or not (and on how to change it) must depend only on x_j for j <= i. This is in contrast to the "classical" adversarial jammer which may base its decisions on its complete knowledge of x. We present a non-trivial upper bound on the amount of information that can be communicated. We show that the achievable rate can be asymptotically no greater than min{1-H(p),(1-4p)^+}. Here H(.) is the binary entropy function, and (1-4p)^+ equals 1-4p for p < 0.25, and 0 otherwise. | |
| dc.description | 8 pages, 1 figure, extended version of paper submitted to the International Symposium on Information Theory, 2009 (ISIT2009) | |
| dc.identifier | https://arxiv.org/abs/0901.1853 | |
| dc.identifier | http://arxiv.org/abs/0901.1853 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/217551 | |
| dc.subject | Information Theory | |
| dc.title | Binary Causal-Adversary Channels | |
| dc.type | text |