Name
Abstract | ||
|---|---|---|
In the classic adversarial communication problem, two parties communicate over a noisy channel in the presence of a malicious jamming adversary. The arbitrarily varying channels (AVCs) offer an elegant framework to study a wide range of interesting adversary models. The optimal throughput or capacity over such AVCs is intimately tied to the underlying adversary model; in some cases, capacity is unknown and the problem is known to be notoriously hard. The omniscient adversary, one which knows the sender’s entire channel transmission a priori, is one of such classic models of interest; the capacity under such an adversary remains an exciting open problem. The myopic adversary is a generalization of that model where the adversary’s observation may be corrupted over a noisy discrete memoryless channel. Through the adversary’s myopicity, one can unify the slew of different adversary models, ranging from the omniscient adversary to one that is completely blind to the transmission (the latter is the well known oblivious model where the capacity is fully characterized).In this work, we present new results on the capacity under both the omniscient and myopic adversary models. We completely characterize the positive capacity threshold over general AVCs with omniscient adversaries. The characterization is in terms of two key combinatorial objects: the set of completely positive distributions and the CP-confusability set. For omniscient AVCs with positive capacity, we present non-trivial lower and upper bounds on the capacity; unlike some of the previous bounds, our bounds hold under fairly general input and jamming constraints. Our lower bound improves upon the generalized Gilbert-Varshamov bound for general AVCs while the upper bound generalizes the well known Elias-Bassalygo bound (known for binary and q-ary alphabets). For the myopic AVCs, we build on prior results known for the so-called sufficiently myopic model, and present new results on the positive rate communication threshold over the so-called insufficiently myopic regime (a completely insufficient myopic adversary specializes to an omniscient adversary). We present interesting examples for the widely studied models of adversarial bit-flip and bit-erasure channels. In fact, for the bit-flip AVC with additive adversarial noise as well as random noise, we completely characterize the omniscient model capacity when the random noise is sufficiently large vis-a-vis the adversary’s budget. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1109/ISIT50566.2022.9834632 | 2022 IEEE International Symposium on Information Theory (ISIT) |
Keywords | DocType | ISSN |
classic adversarial communication problem,malicious jamming adversary,noisy discrete memoryless channel,positive capacity threshold,myopic AVC,adversarial bit-flip,additive adversarial noise,omniscient model capacity,myopic adversary model,omniscient AVC,omniscient adversary model,arbitrarily varying channels,Gilbert-Varshamov bound,Elias-Bassalygo bound,q-ary alphabets,binary alphabets,bit-erasure channel,random noise | Conference | 2157-8095 |
ISBN | Citations | PageRank |
978-1-6654-2160-7 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anuj Kumar Yadav | 1 | 0 | 0.68 |
| Mohammadreza Alimohammadi | 2 | 0 | 0.34 |
| Yihan Zhang | 3 | 0 | 0.68 |
| Amitalok J. Budkuley | 4 | 0 | 0.68 |
| Sidharth Jaggi | 5 | 977 | 92.83 |