Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912147411304448 |
|---|---|
| author | Fawzi, Omar Fermé, Paul |
| author_facet | Fawzi, Omar Fermé, Paul |
| contents | We address the problem of coding for classical broadcast channels, which entails maximizing the success probability that can be achieved by sending a fixed number of messages over a broadcast channel. For point-to-point channels, Barman and Fawzi found in~\cite{BF18} a $(1-e^{-1})$-approximation algorithm running in polynomial time, and showed that it is \textrm{NP}-hard to achieve a strictly better approximation ratio. Furthermore, these algorithmic results were at the core of the limitations they established on the power of non-signaling assistance for point-to-point channels. It is natural to ask if similar results hold for broadcast channels, exploiting links between approximation algorithms of the channel coding problem and the non-signaling assisted capacity region.
In this work, we make several contributions on algorithmic aspects and non-signaling assisted capacity regions of broadcast channels. For the class of deterministic broadcast channels, we describe a $(1-e^{-1})^2$-approximation algorithm running in polynomial time, and we show that the capacity region for that class is the same with or without non-signaling assistance. Finally, we show that in the value query model, we cannot achieve a better approximation ratio than $Ω\left(\frac{1}{\sqrt{m}}\right)$ in polynomial time for the general broadcast channel coding problem, with $m$ the size of one of the outputs of the channel. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_05515 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance Fawzi, Omar Fermé, Paul Information Theory Computational Complexity We address the problem of coding for classical broadcast channels, which entails maximizing the success probability that can be achieved by sending a fixed number of messages over a broadcast channel. For point-to-point channels, Barman and Fawzi found in~\cite{BF18} a $(1-e^{-1})$-approximation algorithm running in polynomial time, and showed that it is \textrm{NP}-hard to achieve a strictly better approximation ratio. Furthermore, these algorithmic results were at the core of the limitations they established on the power of non-signaling assistance for point-to-point channels. It is natural to ask if similar results hold for broadcast channels, exploiting links between approximation algorithms of the channel coding problem and the non-signaling assisted capacity region. In this work, we make several contributions on algorithmic aspects and non-signaling assisted capacity regions of broadcast channels. For the class of deterministic broadcast channels, we describe a $(1-e^{-1})^2$-approximation algorithm running in polynomial time, and we show that the capacity region for that class is the same with or without non-signaling assistance. Finally, we show that in the value query model, we cannot achieve a better approximation ratio than $Ω\left(\frac{1}{\sqrt{m}}\right)$ in polynomial time for the general broadcast channel coding problem, with $m$ the size of one of the outputs of the channel. |
| title | Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance |
| topic | Information Theory Computational Complexity |
| url | https://arxiv.org/abs/2310.05515 |