Codes against Online Adversaries
| dc.creator | Dey, Bikash Kumar | |
| dc.creator | Jaggi, Sidharth | |
| dc.creator | Langberg, Michael | |
| dc.date | 2008-11-18 | |
| dc.date.accessioned | 2026-07-07T10:19:08Z | |
| dc.date.available | 2026-07-07T10:19:08Z | |
| dc.description | In this work we consider the communication of information in the presence of an online 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 symbol-by-symbol over a communication channel. The adversarial jammer can view the transmitted symbols 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. More generally, for a delay parameter 0<d<1, we study the scenario in which the jammer's decision on the corruption of x_i must depend solely on x_j for j < i - dn. In this work, we initiate the study of codes for online adversaries, and present a tight characterization of the amount of information one can transmit in both the 0-delay and, more generally, the d-delay online setting. We prove tight results for both additive and overwrite jammers when the transmitted symbols are assumed to be over a sufficiently large field F. Finally, we extend our results to a jam-or-listen online model, where the online adversary can either jam a symbol or eavesdrop on it. We again provide a tight characterization of the achievable rate for several variants of this model. The rate-regions we prove for each model are informational-theoretic in nature and hold for computationally unbounded adversaries. The rate regions are characterized by "simple" piecewise linear functions of p and d. The codes we construct to attain the optimal rate for each scenario are computationally efficient. | |
| dc.description | 10 pages + abstract + appendix/references. Submitted to STOC 2009 | |
| dc.identifier | https://arxiv.org/abs/0811.2850 | |
| dc.identifier | http://arxiv.org/abs/0811.2850 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/174401 | |
| dc.subject | Information Theory | |
| dc.title | Codes against Online Adversaries | |
| dc.type | text |