Treffer: Approximation Algorithms for Channel Coding and Non-signaling Correlations ; Algorithmes d'approximation pour le problème du codage de canal et corrélations non-signalantes

La recherche de codes efficaces est essentielle pour obtenir des communications fiables sur des canaux bruités. Alors que les codes correcteurs d'erreurs pour les canaux i.i.d. sont bien compris, le problème d'approximer le meilleur code pour un canal générique, c'est-à-dire qui maximise la probabilité de succès de la communication sur les canaux bruités, a été beaucoup moins étudié. Cette thèse aborde ce problème de codage dans plusieurs scénarios.Pour les canaux point-à-point, des algorithmes d'approximation optimaux pour le problème du codage ainsi que le problème du décodage de liste sont connus. Nous étudions une généralisation de ce dernier avec une taille de liste variable, compensée par une probabilité d'échec croissante. Plus généralement, nous étudions le problème de couverture qui consiste à maximiser \sum_{a \in [n]} w_a \varphi(|\{i \in S : a \in T_i\}|) sur les sous-ensembles S \subseteq [m] de cardinal k, pour \varphi une fonction croissante concave quelconque. Nous proposons un algorithme d'approximation pour ce problème de ratio \alpha_{\varphi} := \min_{x \in N^*} \frac{E[\varphi(Poi(x))]}{\varphi(E[Poi(x)])}, qui ne peut être amélioré pour \varphi sous-linéaire si P\not=NP.Pour les canaux à accès multiple, nous montrons que le problème du codage ne peut être approximé avec un ratio constant sous une hypothèse de complexité sur des formules k-SAT aléatoires. En généralisant et en abstrayant l'intrication quantique, les corrélations non-signalantes peuvent être utilisées pour améliorer la communication. Nous montrons que les codes optimaux avec assistance non-signalante pour les canaux à accès multiples peuvent être trouvés en temps polynomial en le nombre de copies du canal. Appliqué au canal additionneur binaire, l'utilisation de corrélations non-signalantes étend sa zone de capacité. Nous fournissons une borne supérieure sur la zone de capacité avec assistance non-signalante. Lorsque l'assistance non-signalante n'est pas partagée entre les encodeurs, nous montrons que la zone de capacité ...