Codes against online adversaries: Large alphabets

Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


In this paper, 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,xn) symbol-by-symbol over a communication channel. The adversarial jammer can view the transmitted symbols xi one at a time and can change up to a p-fraction of them. However, for each symbol x i, the jammer's decision on whether to corrupt it or not (and on how to change it) must depend only on xj for j≤ i. This is in contrast to the 'classical' adversarial jammer which may base its decisions on its complete knowledge of {x. More generally, for a delay parameter δin (0,1), we study the scenario in which the jammer's decision on the corruption of xi must depend solely on xj for j≤ i-δn. In this study, the transmitted symbols are assumed to be over a sufficiently large field \BBF. The sender and receiver do not share resources such as common randomness (though the sender is allowed to use stochastic encoding). We present a tight characterization of the amount of information one can transmit in both the 0-delay and, more generally, the δ-delay online setting. We show that for 0-delay adversaries, the achievable rate asymptotically equals that of the classical adversarial model. For positive values of δ , we consider two types of jamming: additive and overwrite. We also extend our results to a jam-or-listen online model, where the online adversary can either jam a symbol or eavesdrop on it. We present computationally efficient achievability schemes even against computationally unrestricted jammers.

שפה מקוריתאנגלית
מספר המאמר6457452
עמודים (מ-עד)3304-3316
מספר עמודים13
כתב עתIEEE Transactions on Information Theory
מספר גיליון6
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2013

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Codes against online adversaries: Large alphabets'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי