Upper Bounds on the Capacity of Binary Channels With Causal Adversaries

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),..., x(n)) 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 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 a causal manner. Namely, for each bit x(i), the jammer's decision on whether to corrupt it or not must depend only on x(j) 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.