Record Details

DSpace at IIT Bombay

View Archive Info
 

Metadata

 
Field Value
 
Title Codes against online adversaries
 
Names DEY, BK
JAGGI, S
LANGBERG, M
Date Issued 2009 (iso8601)
Abstract 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, 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 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. More generally, for a delay parameter d is an element of (0, 1), we study the scenario in which the jammer's decision on the corruption of xi must depend solely on x(j) for j <= i - dn. In this work, the transmitted symbols are assumed to be over a sufficiently large field F. We 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 show that for 0-delay adversaries, the achievable rate asymptotically equals that of the classical adversarial model. For positive values of d, 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.
Genre Proceedings Paper
Identifier 2009 47TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING, VOLS 1 AND 2,1169-1176