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.
Gratuit