Upper bounds on the capacity of binary channels with causal adversaries

Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg, Anand D. Sarwate

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


In this paper, 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,..., xn) bit-by-bit over a communication channel. The sender and the receiver do not share common randomness. The adversarial jammer can view the transmitted bits xi one at a time and can change up to a p-fraction of them. However, the decisions of the jammer must be made in a causal manner. Namely, for each bit xi, the jammer's decision on whether to corrupt it or not must depend only on xj for j ≤ i. This is in contrast to the 'classical' adversarial jamming situations in which the jammer has no knowledge of x, or knows x completely. In this study, we present upper bounds (that hold under both the average and maximal probability of error criteria) on the capacity which hold for both deterministic and stochastic encoding schemes.

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

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Upper bounds on the capacity of binary channels with causal adversaries'. יחד הם יוצרים טביעת אצבע ייחודית.

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