Agenda de l'ENS de Lyon

Approximation Algorithms for Channel Coding and Non-Signaling Correlations

mer 29 nov 2023



Soutenance de thèse de monsieur FERME Paul. Sous la direction de monsieur FAWZI Omar.

Langue(s) des interventions
Description générale

Finding efficient codes is crucial for achieving reliable communication over noisy channels. While error-correcting codes for i.i.d. channels are well understood, the task of approximating the best code for a general channel, i.e. that maximizes the success probability of the encoding and decoding process, is much less developed. This thesis addresses this problem in several scenarios.

For point-to-point channels, optimal approximation algorithms for coding and list-decoding are known. We study a generalization of the latter with a variable list size, compensated by an increasing probability of failure. More generally, we study the coverage problem which entails maximizing \sum_{a \in [n]} w_a \varphi(|\{i \in S : a \in T_i\}|) over subsets S \subseteq [m] of cardinality k, for a general nondecreasing concave function \varphi. We provide an approximation algorithm for that problem of ratio \alpha_{\varphi} := \min_{x \in N^*} \frac{E[\varphi(Poi(x))]}{\varphi(E[Poi(x)])}, which cannot be improved for sublinear \varphi if P\not=NP.

For multiple-access channels, we show that the coding problem cannot be approximated within any constant ratio under some complexity hypothesis on random k-SAT formulas. Generalizing and abstracting quantum entanglement, non-signaling correlations can be used to enhance communication. We show that optimal non-signaling codes can be found in polynomial time in the number of copies of the channel. Applied to the binary adder channel, a non-signaling advantage on its capacity region is established. We provide a general single-letter outer bound on the non-signaling capacity region. When non-signaling assistance is not shared between encoders, we show that the capacity region is not changed.

For broadcast channels, when restricted to deterministic channels, we provide a (1−1/e)^2-approximation algorithm for the unassisted coding problem, and we show that their capacity region is not changed with non-signaling assistance. In the value query model, we show that we cannot achieve a better approximation ratio than \Omega(\frac{1}{\sqrt{m}) for the general broadcast channel coding problem, with m the output size of the channel.


Mots clés