---
_id: '12017'
abstract:
- lang: eng
text: '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.'
article_processing_charge: No
author:
- first_name: Anuj Kumar
full_name: Yadav, Anuj Kumar
last_name: Yadav
- first_name: Mohammadreza
full_name: Alimohammadi, Mohammadreza
last_name: Alimohammadi
- first_name: Yihan
full_name: Zhang, Yihan
id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
last_name: Zhang
orcid: 0000-0002-6465-6258
- first_name: Amitalok J.
full_name: Budkuley, Amitalok J.
last_name: Budkuley
- first_name: Sidharth
full_name: Jaggi, Sidharth
last_name: Jaggi
citation:
ama: 'Yadav AK, Alimohammadi M, Zhang Y, Budkuley AJ, Jaggi S. New results on AVCs
with omniscient and myopic adversaries. In: 2022 IEEE International Symposium
on Information Theory. Vol 2022. Institute of Electrical and Electronics Engineers;
2022:2535-2540. doi:10.1109/ISIT50566.2022.9834632'
apa: 'Yadav, A. K., Alimohammadi, M., Zhang, Y., Budkuley, A. J., & Jaggi, S.
(2022). New results on AVCs with omniscient and myopic adversaries. In 2022
IEEE International Symposium on Information Theory (Vol. 2022, pp. 2535–2540).
Espoo, Finland: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ISIT50566.2022.9834632'
chicago: Yadav, Anuj Kumar, Mohammadreza Alimohammadi, Yihan Zhang, Amitalok J.
Budkuley, and Sidharth Jaggi. “New Results on AVCs with Omniscient and Myopic
Adversaries.” In 2022 IEEE International Symposium on Information Theory,
2022:2535–40. Institute of Electrical and Electronics Engineers, 2022. https://doi.org/10.1109/ISIT50566.2022.9834632.
ieee: A. K. Yadav, M. Alimohammadi, Y. Zhang, A. J. Budkuley, and S. Jaggi, “New
results on AVCs with omniscient and myopic adversaries,” in 2022 IEEE International
Symposium on Information Theory, Espoo, Finland, 2022, vol. 2022, pp. 2535–2540.
ista: 'Yadav AK, Alimohammadi M, Zhang Y, Budkuley AJ, Jaggi S. 2022. New results
on AVCs with omniscient and myopic adversaries. 2022 IEEE International Symposium
on Information Theory. ISIT: Internation Symposium on Information Theory vol.
2022, 2535–2540.'
mla: Yadav, Anuj Kumar, et al. “New Results on AVCs with Omniscient and Myopic Adversaries.”
2022 IEEE International Symposium on Information Theory, vol. 2022, Institute
of Electrical and Electronics Engineers, 2022, pp. 2535–40, doi:10.1109/ISIT50566.2022.9834632.
short: A.K. Yadav, M. Alimohammadi, Y. Zhang, A.J. Budkuley, S. Jaggi, in:, 2022
IEEE International Symposium on Information Theory, Institute of Electrical and
Electronics Engineers, 2022, pp. 2535–2540.
conference:
end_date: 2022-07-01
location: Espoo, Finland
name: 'ISIT: Internation Symposium on Information Theory'
start_date: 2022-06-26
date_created: 2022-09-04T22:02:06Z
date_published: 2022-08-03T00:00:00Z
date_updated: 2025-09-10T09:45:03Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834632
external_id:
isi:
- '001254261902116'
intvolume: ' 2022'
isi: 1
language:
- iso: eng
month: '08'
oa_version: None
page: 2535-2540
publication: 2022 IEEE International Symposium on Information Theory
publication_identifier:
isbn:
- '9781665421591'
issn:
- 2157-8095
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: New results on AVCs with omniscient and myopic adversaries
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 2022
year: '2022'
...