Technical Program

Paper Detail

Paper Title The Interplay of Causality and Myopia in Adversarial Channel Models
Paper IdentifierTU2.R9.2
Authors Bikash Kumar Dey, Indian Institute of Technology, Bombay, India; Sidharth Jaggi, Chinese University of Hong Kong, Hong Kong SAR of China; Michael Langberg, University at Buffalo, United States; Anand D. Sarwate, Rutgers University, United States; Carol Wang, Independent Researcher, United States
Session Channel Models
Location Pontoise, Level 5
Session Time Tuesday, 09 July, 11:40 - 13:00
Presentation Time Tuesday, 09 July, 12:00 - 12:20
Manuscript  Click here to download the manuscript
Abstract The difference in capacity formulae between worst-case and average-case channel noise models has been part of information theory since the early days of the field. This paper continues a line of work studying intermediate models in which the channel behavior can depend partially on the transmitted codeword. In particular, we consider a model in which a binary erasure channel (with maximum fraction of erasures $p$) is controlled by an adversary who can observe the transmitted codeword through an independent and memoryless erasure channel (with erasure probability $q$). Upper and lower bounds on the capacity are given for two models: a noncausal model, in which the adversary can choose their erasures based on the entire (partially observed) codeword, and a causal model, in which at each time the adversary must choose its erasures based on the current and previously observed codeword bits. The achievable rate for the noncausal case is larger than the Gilbert-Varshamov bound and for some parameter ranges exceeds the linear programming (LP) bound; we also provide a non-trivial outer bound on the capacity. For the causal case, we show the capacity is $1 - 2p + q$ for $p \geq q$ (prior work shows the capacity to equal $1-p$ when $p