Sliding Window Adversarial Channels
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915263139545088 |
|---|---|
| author | Dey, Bikash Kumar Jaggi, Sidharth Langberg, Michael Sarwate, Anand D. Zhang, Yihan |
| author_facet | Dey, Bikash Kumar Jaggi, Sidharth Langberg, Michael Sarwate, Anand D. Zhang, Yihan |
| contents | In an arbitrarily varying channel (AVC), the channel has a state which is under the control of an adversarial jammer and the corresponding capacities are often functions of the "power" constraints on the transmitter and jammer. In this paper we propose a model in which the constraints must hold almost surely over contiguous subsequences of the codeword and state, which we call a sliding window constraint. We study oblivious jammers and codes with stochastic encoding under maximum probability of error. We show that this extra limitation on the jammer is beneficial for the transmitter: in some cases, the capacity for unique decoding with a sliding window constraint is equal to the capacity for list decoding in the standard model without sliding windows, roughly implying that the addition of window constraints reduces list decoding to unique decoding. The list decoding capacity in the standard model can be strictly larger than the unique decoding capacity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_19773 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sliding Window Adversarial Channels Dey, Bikash Kumar Jaggi, Sidharth Langberg, Michael Sarwate, Anand D. Zhang, Yihan Information Theory 94A40 In an arbitrarily varying channel (AVC), the channel has a state which is under the control of an adversarial jammer and the corresponding capacities are often functions of the "power" constraints on the transmitter and jammer. In this paper we propose a model in which the constraints must hold almost surely over contiguous subsequences of the codeword and state, which we call a sliding window constraint. We study oblivious jammers and codes with stochastic encoding under maximum probability of error. We show that this extra limitation on the jammer is beneficial for the transmitter: in some cases, the capacity for unique decoding with a sliding window constraint is equal to the capacity for list decoding in the standard model without sliding windows, roughly implying that the addition of window constraints reduces list decoding to unique decoding. The list decoding capacity in the standard model can be strictly larger than the unique decoding capacity. |
| title | Sliding Window Adversarial Channels |
| topic | Information Theory 94A40 |
| url | https://arxiv.org/abs/2504.19773 |