messages (the bidders) and the output space $\mathcal{Y}_1 := [m]$ with $m := k_1^2$ (the items). Then, we choose uniformly at random an equi-partition of $\mathcal{Y}_1$ in $k_1$ parts of size $k_1$, which we name $T_1, \dots, T_{k_1}$.

Let us define now $\mathcal{Y}_2 := [m + k_1 + 1]$. We take $\mathcal{X} := \mathcal{Y}_2 = [m + 1 + k_1]$ as well. We can now define our broadcast channel $W$, with some positive constant $C$ to be fixed later to guarantee that $W$ is a conditional probability distribution. Let us define its value for $y_2 = 1$:

$$W(y_1 1 | x) := C \times \begin{cases} m^{2\delta} \mathbb{1}_{y_1=x} & \text{when } 1 \le x \le m, \\ \frac{1}{m^{\frac{1}{2}-\delta}} & \text{when } x = m+1, \\ \mathbb{1}_{y_1 \in T_j} & \text{when } 1 \le j := x - (m+1) \le k_1. \end{cases}$$

Then, we define other $y_2$ inputs as translations of $W(y_1 1|x)$. Specifically, we define:

$$W(y_1 y_2 | x) := W(y_1 1 | t_{y_2-1}(x)) \text{ with } t_s(x) := 1 + [(x - 1 + s) \mod (m + k_1 + 1)].$$

All coefficients are nonnegative. So $W$ will be a channel if for all $x$, $\sum_{y_1, y_2} W(y_1 y_2 | x) = 1$. However, one has, for some fixed $x_0$:

$$\begin{align}
\sum_{y_1, y_2} W(y_1 y_2 | x_0) &= \sum_{y_1} \sum_{y_2} W(y_1 y_2 | x_0) = \sum_{y_1} \sum_{y_2} W(y_1 1 | t_{y_2-1}(x_0)) = \sum_{y_1} \sum_{x} W(y_1 1 | x) \nonumber \\
&= C \sum_{y_1} \left[ \sum_{1 \le i \le m} m^{2\delta} \mathbb{1}_{y_1=i} + \frac{1}{m^{\frac{1}{2}-\delta}} + \sum_{1 \le j \le k_1} \mathbb{1}_{y_1 \in T_j} \right] \nonumber \\
&= C \left[ \sum_{1 \le i \le m} m^{2\delta} + m \times \frac{1}{m^{\frac{1}{2}-\delta}} + \sum_{1 \le j \le k_1} k_1 \right] \nonumber \\
&= 1, \tag{5.41}
\end{align}$$

by choosing $C = \frac{1}{m^{1+2\delta}+m^{\frac{1}{2}+\delta}+m}$, which does not depend on $x_0$. Thus, we have defined a correct instance of our problem. Note that on this instance, we have:

$$\begin{align}
f_W^1(S) &= \frac{1}{|\mathcal{Y}_2|} \sum_{y_2} \max_x \sum_{y_1 \in S} W(y_1 y_2 | x) = \sum_{y_2} \max_x \sum_{y_1 \in S} W(y_1 1 | t_{y_2-1}(x)) \nonumber \\
&= \frac{m+k_1+1}{|\mathcal{Y}_2|} \max_x \sum_{y_1 \in S} W(y_1 1 | x) \quad \text{since } t_{y_2-1} \text{ bijection} \tag{5.42} \\
&= \frac{C(m+k_1+1)}{|\mathcal{Y}_2|} \times \max \begin{cases} m^{2\delta} |\{i\} \cap S| & \text{for } 1 \le i \le m \\ \frac{1}{m^{\frac{1}{2}-\delta}} |S| & \text{for } 1 \le j \le k_1 \end{cases} \nonumber
\end{align}$$

Let us also consider an alternate broadcast channel $W'$, with the only difference that $\mathbb{1}_{y_1 \in T_j}$ is replaced by $\frac{1}{m^{\frac{1}{2}}}$, for $j \in [k_1]$. For that channel, the constant $C$ remains the same (since
$\sum_j \sum_{y_1} 1_{y_1 \in T_j} = k_1 \times k_1 = k_1 \times m \times \frac{1}{k_1} = \sum_j \sum_{y_1} \frac{1}{m^2}$, so we get that:

$$ 
\begin{align} 
f_{W'}^1(S) &= \frac{C(m + k_1 + 1)}{|\mathcal{Y}_2|} \times \max \left\{ \begin{array}{ll} m^{2\delta} |\{i\} \cap S| & \text{for } 1 \le i \le m \\ \frac{1}{m^{\frac{1}{2}-\delta}} |S| & \text{for } 1 \le j \le k_1 \end{array} \right. \tag{5.43} \\ 
&= \frac{C(m + k_1 + 1)}{|\mathcal{Y}_2|} \times \max \left\{ \begin{array}{ll} m^{2\delta} |\{i\} \cap S| & \text{for } 1 \le i \le m \\ \frac{1}{m^{\frac{1}{2}-\delta}} |S| & \text{for } 1 \le j \le k_1 \end{array} \right. 
\end{align} 
$$

since $\frac{1}{m^2}|S| \le \frac{1}{m^{\frac{1}{2}-\delta}}|S|$. Let us consider normalized versions $v(S) := \frac{|\mathcal{Y}_2|}{C(m+k_1+1)}f_W^1(S)$ and $v'(S) := \frac{|\mathcal{Y}_2|}{C(m+k_1+1)}f_{W'}^1(S)$, so distinguishing between $v$ and $v'$ is the same as distinguishing between $f_W^1$ and $f_{W'}^1$. We will prove that it takes an exponential number of value queries to distinguish between $v$ and $v'$. On the one hand, one can easily show that the maximum value of the social welfare problem with $v'$ is $(k_1 - 1)m^{2\delta} + \frac{1}{m^{\frac{1}{2}-\delta}}(m - (k_1 - 1)) = O(m^{\frac{1}{2}+2\delta})$, obtained taking $(k_1 - 1)$ singletons as the first components of the partition (the bidders), giving the rest of $\mathcal{Y}_1$ (the items) to the last. On the other hand, the maximum value of the social welfare problem with $v$ is $k_1 \times k_1 = m$, obtained with the partition $T_1, \dots, T_{k_1}$. The fact that it requires an exponential number of value queries to distinguish between the two situations will imply that one cannot get an approximation rate better than $\Omega(\frac{1}{m^{\frac{1}{2}-2\delta}})$ in less than an exponential number of value queries.

We will now prove that distinguishing between $v$ and $v'$ requires an exponential number of value queries. Note first that $v(\emptyset) = v'(\emptyset) = 0$, so we do not need to consider empty sets.

Let us fix some non-empty set $S \subseteq [m]$. Let us define the random boolean variables $X_j^i := 1_{i \in T_j}$ for $j \in [k_1]$ and $i \in [m]$. By construction of the random equi-partition $T_1, \dots, T_{k_1}$, $(X_j^i)_{i \in [m]}$ is a permutation distribution (see Definition 2.3) of $(0, \dots, 0, 1, \dots, 1)$ with $m - k_1$ zeros and $k_1$ ones, each $X_j^i$ following a Bernoulli law of parameter $p := \frac{1}{k_1}$. Thus it is negatively associated by Proposition 2.8, and the sub-family $(X_j^i)_{i \in S}$ is negatively associated as well by Proposition 2.4. Note in particular that $|T_j \cap S| = \sum_{i \in S} X_j^i$ is a sum of negatively associated Bernoulli variables of the same parameter $p$, so the version of the Chernoff-Hoeffding bound from Proposition 2.10 holds.

Let us first assume that $S$ is of size $0 < |S| \le m^{\frac{1}{2}+\delta}$. Then, we have that $\frac{1}{m^{\frac{1}{2}-\delta}}|S| \le m^{2\delta}$, so we get that $v'(S) = m^{2\delta}$. On the other hand, we have that:

$$ v(S) = \max \left\{ \begin{array}{ll} m^{2\delta} & \text{for } 1 \le j \le k_1 \\ |T_j \cap S| & \text{for } 1 \le j \le k_1 \end{array} \right. \tag{5.44} $$
Thus, $v(S)$ is different from $v'(S)$ if and only if $\exists j \in [k_1], |T_j \cap S| > m^{2\delta}$. But, we have:

$$
\begin{align*}
\mathbb{P}(\exists j \in [k_1], |T_j \cap S| > m^{2\delta}) &\le \sum_{j \in [k_1]} \mathbb{P}(|T_j \cap S| > m^{2\delta}) \quad \text{by union bound} \\
&= \sum_{j \in [k_1]} \mathbb{P}\left(\sum_{i \in S} X_j^i > m^{2\delta}\right) = \sum_{j \in [k_1]} \mathbb{P}\left(\frac{1}{|S|} \sum_{i \in S} X_j^i > \left(1 + \frac{\frac{m^{2\delta}}{|S|} - 1}{p}\right) p\right) \\
&\le \sum_{j \in [k_1]} \mathbb{P}\left(\frac{1}{|S|} \sum_{i \in S} X_j^i > \left(1 + \frac{\frac{m^{2\delta}}{|S|}}{p}\right) p\right) \\
&\le \sum_{j \in [k_1]} \exp\left(-\frac{p|S|}{4} \left(\frac{m^{2\delta}}{|S|}\right)^2\right) \quad \text{by Proposition 2.10} \\
&= \sum_{j \in [k_1]} \exp\left(-\frac{1}{4p|S|} m^{4\delta}\right) \le \sum_{j \in [k_1]} \exp\left(-\frac{m^{-\delta}}{4} m^{4\delta}\right) \quad \text{since } \frac{1}{p|S|} = \frac{k_1}{|S|} \ge m^{-\delta} \\
&= m^{\frac{1}{2}} e^{-\frac{m^{3\delta}}{4}}. \tag{5.45}
\end{align*}
$$

Thus, this event occurs with exponentially small probability (on the choice of the partition $T_1, \dots, T_{k_1}$).

Let us now study the case of $S$ of size $|S| > m^{\frac{1}{2}+\delta}$. Then, we have that $\frac{1}{m^{\frac{1}{2}-\delta}}|S| > m^{2\delta}$, so we get that $v'(S) = \frac{1}{m^{\frac{1}{2}-\delta}}|S|$. On the other hand, we have that:

$$
v(S) = \max \left\{ \begin{array}{ll} \frac{1}{m^{\frac{1}{2}-\delta}} |S| & |T_j \cap S| \text{ for } 1 \le j \le k_1 \\ \\ \frac{1}{m^{\frac{1}{2}-\delta}} |S| & |T_j \cap S| > \frac{1}{m^{\frac{1}{2}-\delta}} |S|. \end{array} \right. \tag{5.46}
$$

Thus, $v(S)$ is different from $v'(S)$ if and only if $\exists j \in [k_1], |T_j \cap S| > \frac{1}{m^{\frac{1}{2}-\delta}}|S|$. But, we
have:

$$
\begin{align*}
\mathbb{P}\left(\exists j \in [k_1], |T_j \cap S| > \frac{1}{m^{\frac{1}{2}-\delta}}|S|\right) &\le \sum_{j \in [k_1]} \mathbb{P}\left(|T_j \cap S| > \frac{1}{m^{\frac{1}{2}-\delta}}|S|\right) \quad \text{by union bound} \\
&= \sum_{j \in [k_1]} \mathbb{P}\left(\sum_{i \in S} X_j^i > \frac{1}{m^{\frac{1}{2}-\delta}}|S|\right) = \sum_{j \in [k_1]} \mathbb{P}\left(\frac{1}{|S|} \sum_{i \in S} X_j^i > \left(1 + \frac{\frac{1}{|S|} \frac{1}{m^{\frac{1}{2}-\delta}} |S| - 1}{p}\right) p\right) \\
&\le \sum_{j \in [k_1]} \mathbb{P}\left(\frac{1}{|S|} \sum_{i \in S} X_j^i > \left(1 + \frac{\frac{1}{m^{\frac{1}{2}-\delta}}}{p}\right) p\right) \\
&= \sum_{j \in [k_1]} \mathbb{P}\left(\frac{1}{|S|} \sum_{i \in S} X_j^i > (1 + m^\delta)p\right) \quad \text{since } p = \frac{1}{k_1} = \frac{1}{m^{\frac{1}{2}}} \\
&\le \sum_{j \in [k_1]} \exp\left(-\frac{p|S|}{4}m^{2\delta}\right) \quad \text{by Proposition 2.10} \\
&\le \sum_{j \in [k_1]} \exp\left(-\frac{m^\delta}{4}m^{2\delta}\right) \quad \text{since } p|S| = \frac{|S|}{k_1} \ge m^\delta \\
&= m^{\frac{1}{2}}e^{-\frac{m^{3\delta}}{4}}. \tag{5.47}
\end{align*}
$$

Thus, this event occurs with exponentially small probability as well. We have then that for all set S, $\mathbb{P}(v(S) \neq v'(S)) \leq p_{\text{leak}} := m^{\frac{1}{2}}e^{-\frac{m^{3\delta}}{4}}$, which is an exponentially small bound that does not depend on S.

Hence, for every set S, only with exponentially small probability $p_{\text{leak}}$ can one distinguish between v and v'. For some fixed algorithm $\mathcal{A}$, let us consider the sequence L of queries made by $\mathcal{A}$ before it is able to distinguish between v and v': $L := (S_1, \dots, S_n)$, with $v(S_i) = v'(S_i)$ for $i \in [n]$ and $v'(S_{n+1}) > v(S_{n+1})$. L is independent of $T_1, \dots, T_{k_1}$ as no information from this partition is leaked before $S_{n+1}$. Thus, for such an algorithm to be correct, it should work for any equi-partition $T_1, \dots, T_{k_1}$. We have:

$$ \mathbb{P} (\exists i \in [n] : v(S_i) \neq v'(S_i)) \leq \sum_{i=1}^{n} \mathbb{P} (v(S_i) \neq v'(S_i)) = n p_{\text{leak}} \text{ by union bound.} $$

In particular, this implies that:

$$ \mathbb{P} (\forall i \in [n] : v(S_i) = v'(S_i)) \geq 1 - n p_{\text{leak}}. $$

So, if $1 - np_{\text{leak}} > 0$, i.e. $n < \frac{1}{p_{\text{leak}}}$, then there exists some equi-partition $T_1, \dots, T_{k_1}$ such that our algorithm outputs a sequence L of queries of length n before being able to distinguish between v and v'. In particular, we can take $n = \frac{1}{2p_{\text{leak}}}$ so that L is of exponential size. Hence, for any algorithm $\mathcal{A}$, there exists some equi-partition $T_1, \dots, T_{k_1}$ such that $\mathcal{A}$ needs an exponential number of value queries to distinguish between v and v'. This concludes the proof of the theorem for any deterministic algorithm.

Finally, the hardness result holds also for randomized algorithms. Indeed, let us call $\mathcal{A}_s$, the running algorithm conditioned on its random bits being s. $\mathcal{A}_s$ is deterministic so the
previous proof holds: with high probability $p$, the sequence of $\lfloor \frac{1-p}{p_{\text{leak}}} \rfloor$ queries does not
reveal anything to distinguish between $v$ and $v'$, although it is of exponential size in $m$.
Then, averaging over all its random bitstrings, the same result holds, as $p_{\text{leak}}$ is independent
of the equi-partition $T_1, \dots, T_{k_1}$.
$\square$

5.4.3 Limitations of the Model

The main weakness of the previous result is that it highly relies on the restriction that one has access to the data only through value queries. Indeed, if one has access to the full data, it is possible to read the partition $T_1, \dots, T_{k_1}$ which gives the optimal solution directly. This weakness comes from the fact that our utility function $f_W^1$ can be described by polynomial-size data, as it is characterized by a broadcast channel $W$, whereas one usually consider any XOS functions, in particular with some having inherently an exponential-size defining set of linear valuation functions.

On the other hand, one can also remark that when $f_W^1$ is written as a maximum of linear valuation functions, then that defining set of linear valuation functions is of exponential size. Hence, we think that it is still relevant to study the value query complexity of such a family of functions, as it is not clear how one could recover the partition in polynomial time from this exponential-size set of linear valuations without any additional information.

5.5 Conclusion

In this chapter, we have studied several algorithmic aspects and non-signaling assisted capacity regions of broadcast channels. We have shown that sum success probabilities of the broadcast channel coding problem are the same with and without non-signaling assistance between decoders, and that it implied that non-signaling resource shared between decoders does not change the capacity region. For the class of deterministic broadcast channels, we have described a $(1 - e^{-1})^2$-approximation algorithm running in polynomial time, and we have shown that the capacity region for that class is the same with or without non-signaling assistance. Finally, we have shown that in the value query model, we cannot achieve a better approximation ratio than $\Omega(\frac{1}{\sqrt{m}})$ in polynomial time for the general broadcast channel coding problem, with $m$ the size of one of the outputs of the channel.

Our results suggest that non-signaling assistance could improve the capacity region of general broadcast channels, which is left as a major open question. An intermediate result would be to show that it is NP-hard to approximate the broadcast channel coding problem within any constant ratio, strengthening our hardness result without relying on the value query model. Finally, one could also try to develop approximations algorithms for other sub-classes of broadcast channels, such as semi-deterministic or degraded ones. This could be a crucial step towards showing that the capacity region for those classes is the same with or without non-signaling assistance.
Conclusion

In this thesis, we have studied several channel coding problems, with and without non-
signaling assistance, from the point of view of algorithmic approximation and of capacity
regions.

In Chapter 3, we have introduced a generalization of the maximum *l*-multi-coverage prob-
lem which entails maximizing the quantity $\sum_{a \in [n]} w_a \varphi(|\{i \in S : a \in T_i\}|)$ over subsets
$S \subseteq [m]$ of cardinality $k$. We have shown that when $\varphi$ is normalized, nondecreasing
and concave, we can obtain an approximation guarantee given by the *Poisson concavity
ratio* $\alpha_{\varphi} := \min_{x \in \mathbb{N}^*} \frac{\mathbb{E}[\varphi(\mathrm{Poi}(x))]}{\varphi(\mathbb{E}[\mathrm{Poi}(x)])}$ and we showed it is tight for sublinear functions $\varphi$ if
$P \neq \mathrm{NP}$. Applied to channel coding, and more specifically to $\varphi$-list-decoding, where the
length restriction on the list of guesses of the decoder in $l$-list-decoding is replaced by a
probability $\frac{\varphi(l)}{l}$ of correctly decoding a list of guesses of variable size $l$, we have obtained
a tight approximation guarantee $\alpha_{\varphi}$ for the class of channels $W$ of the form $W(y|x) = \frac{1}{t}$
for $y \in T_x$ with $|T_x| = t$ and $W(y|x) = 0$ elsewhere. A natural open question is whether
the NP-hardness guarantee can be extended for $\varphi(n) \neq o(n)$. Another open problem is to
extend the $\alpha_{\varphi}$-approximation algorithm for $\varphi$-list-decoding on all channels.

In Chapter 4, we have shown that the multiple-access channel coding problem cannot be
approximated within any constant ratio under a complexity hypothesis on random k-SAT
formulas. We have shown that optimal non-signaling assisted codes for multiple-access
channels 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 has been
established. We have provided a general single-letter outer bound on the non-signaling
capacity region. When non-signaling assistance is not shared between encoders, we have
shown that the capacity region is not changed. A remaining open question is whether
quantum entanglement may increase the capacity of the binary adder channel. Also,
establishing a single-letter formula for the non-signaling assisted capacity of multiple-
access channels is the main open question left here, which could be obtained by achieving
the provided single-letter outer bound on the non-signaling capacity region.

In Chapter 5, for the class of deterministic broadcast channels, we have provided a $(1-e^{-1})^2$-approximation algorithm for the unassisted coding problem, and we have shown that their capacity region is not changed with non-signaling assistance. In the value query model, we have shown 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. Our
results suggest that non-signaling assistance could improve the capacity region of general broadcast channels, which is left as a major open question. An intermediate result would be to show that it is NP-hard to approximate the broadcast channel coding problem within any constant ratio, strengthening our hardness result without relying on the value query model.

Throughout this thesis, we have shown that links between approximation algorithms for channel coding and non-signaling assisted capacity regions are fruitful in both directions. On the one hand, the existence of approximation algorithms with constant ratio for channel coding results often in the absence of non-signaling advantage on the related capacity regions. On the other hand, the hardness of approximation within any constant ratio for the channel coding problem results often in the existence of a non-signaling advantage on the related capacity regions. Although not a formal equivalence, this strong link between those apparently unrelated domains may be the key to address unsolved problems from both topics. In particular, the step achieved in the understanding of the influence of non-signaling correlations on broadcast channels, solved now for deterministic channels, goes in that direction, and could be extended to other classes of channels. We believe that this connection deserves more attention. In fact, as the complexity-theoretic point of view on entangled multiplayer games was extremely fruitful [JNV$^{+20}$], we expect the algorithmic study of problems arising in information theory to achieve important insights.
Conclusion

Dans cette thèse, nous avons étudié plusieurs problèmes de codage de canal, avec et sans
assistance non-signalante, du point de vue de l'approximation algorithmique et des zones
de capacité.

Dans le Chapitre 3, nous avons introduit une généralisation du problème de couverture
multiple maximale de paramètre $\ell$ où l'on maximise $\sum_{a \in [n]} w_a \varphi(|\{i \in S : a \in T_i\}|)$ sur
les sous-ensembles $\subseteq [m]$ de cardinal $k$. Nous avons montré que lorsque $\varphi$ est normalisée,
croissante et concave, nous pouvons obtenir une garantie d'approximation donnée par le
rapport de concavité de Poisson $\alpha_{\varphi} := \min_{x \in \mathbb{N}^*} \frac{\mathbb{E}[\varphi(\text{Poi}(x))]}{\varphi(\mathbb{E}[\text{Poi}(x)])}$ et nous avons montré qu'elle est
optimale pour les fonctions sous-linéaires $\varphi$ si $P \neq \text{NP}$. Appliqué au codage de canal, et
plus spécifiquement au décodage de liste de paramètre $\varphi$, où la restriction de longueur
sur la liste de suppositions du décodeur dans le décodage de liste de paramètre $\ell$ est
remplacée par une probabilité $\frac{\varphi(\ell)}{\ell}$ de décodeur correctement une liste de suppositions
de taille variable $\ell$, nous avons obtenu une stricte garantie d'approximation $\alpha_{\varphi}$ pour la
classe de canaux $W$ de la forme $W(y|x) = \frac{1}{t}$ pour $y \in T_x$ avec $|T_x| = t$ et $W(y|x) = 0$
ailleurs. Une question ouverte naturelle est de savoir si la garantie de NP-difficulté peut
être étendue pour $\varphi(n) \neq o(n)$. Un autre problème ouvert consiste à étendre l'algorithme
d'approximation $\alpha_{\varphi}$ pour le décodage de listes de paramètre $\varphi$ sur tous les canaux.

Dans le Chapitre 4, nous avons montré que le problème du codage des canaux à accès
multiple ne peut être approximé avec un ratio constant sous une hypothèse de complexité sur
les formules $k$-SAT aléatoires. Nous avons montré que les codes optimaux avec assistance
non-signalante pour les canaux à accès multiple peuvent être trouvés en temps polynomial
en le nombre de copies du canal. Appliqué au canal additionneur binaire, un avantage
non-signalant sur sa zone de capacité a été établi. Nous avons fourni une borne supérieure
générale à une seule lettre pour la zone de capacité non-signalante. Lorsque l'assistance
non-signalante n'est pas partagée entre les encodeurs, nous avons montré que la zone de
capacité n'est pas modifiée. La question de savoir si l'intrication quantique peut augmenter
la capacité du canal additionneur binaire reste ouverte. En outre, l'établissement d'une
formule à une seule lettre pour la capacité avec assistance non-signalante des canaux à
accès multiple reste la principale question ouverte de ce chapitre. Cette dernière pourrait
être obtenue en montrant que la borne supérieure à une seule lettre fournie pour la zone
de capacité non-signalante peut en fait être atteinte.

Dans le Chapitre 5, pour la classe des canaux de diffusion déterministes, nous avons
fourni un algorithme d'approximation de ratio $(1 - e^{-1})^2$ pour le problème du codage sans
assistance, et nous avons montré que leur zone de capacité n'est pas modifiée par l'assistance
non-signalante. Dans le modèle d'accès par valeur, nous avons montré que nous ne pouvons
pas obtenir un meilleur ratio d'approximation que $\Omega\left(\frac{1}{\sqrt{m}}\right)$ pour le problème de codage du
canal de diffusion général, avec $m$ la taille de sortie du canal. Nos résultats suggèrent que
l'assistance non-signalante pourrait améliorer la zone de capacité des canaux de diffusion
généraux, ce qui reste une question ouverte majeure. Un résultat intermédiaire consisterait
à montrer qu'il est NP-difficile d'approximer le problème de codage des canaux de diffusion
pour n'importe quel ratio constant, ce qui renforcerait notre résultat de difficulté sans
s'appuyer sur le modèle d'accès par valeur.

Tout au long de cette thèse, nous avons montré que les différents liens entre les algo-
rithmes d'approximation pour le codage de canal et les zones de capacité avec assistance
non-signalantes sont fructueux dans les deux sens. D'une part, l'existence d'algorithmes
d'approximation à rapport constant pour le codage de canal se traduit souvent par l'absence
d'avantage non-signalant pour les zones de capacité correspondantes. D'autre part, la
difficulté d'approximation pour un ratio constant quelconque pour le problème du codage
de canal se traduit souvent par l'existence d'un avantage non-signalant dans les zones de
capacité correspondantes. Bien qu'il ne s'agisse pas d'une équivalence formelle, ce lien
étroit entre ces domaines apparemment sans rapport peut être la clé pour résoudre des
problèmes non résolus dans les deux domaines. En particulier, l'étape franchie dans la
compréhension de l'influence des corrélations non-signalantes sur les canaux de diffusion,
résolue à présent pour les canaux déterministes, va dans cette direction et pourrait être
étendue à d'autres classes de canaux. Nous pensons que ce lien mérite plus d'attention.
En fait, comme le point de vue de la théorie de la complexité sur les jeux multijoueurs
intriqués a été extrêmement fructueux [JNV+20], nous nous attendons à ce que l'étude
algorithmique des problèmes posés par la théorie de l'information aboutisse à des résultats
importants.
Bibliography

[AA00] Erling D Andersen and Knud D Andersen. The Mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm. In *High performance optimization*, pages 197-232. Springer, 2000. doi:10.1007/978-1-4757-3216-0_8. Citations: § 86

[AAM+11] Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein. Inapproximability of densest $\kappa$-subgraph from average case hardness. *Unpublished manuscript*, 1, 2011. URL: https://www.tau.ac.il/~nogaa/PDFS/dks8.pdf. Citations: § 70, 71, 73, and 111

[AB99] Rudolf Ahlswede and Vladimir B. Balakirsky. Construction of uniquely decodable codes for the two-user binary adder channel. *IEEE Trans. Inf. Theory*, 45(1):326-330, 1999. doi:10.1109/18.746834. Citations: § 86

[ADR82] Alain Aspect, Jean Dalibard, and Gérard Roger. Experimental test of Bell's inequalities using time-varying analyzers. *Phys. Rev. Lett.*, 49:1804-1807, Dec 1982. doi:10.1103/PhysRevLett.49.1804. Citations: § 2 and 6

[Ahl73] Rudolf Ahlswede. Multi-way communication channels. In *2nd International Symposium on Information Theory, Tsahkadsor, Armenia, USSR, September 2-8, 1971*, pages 23-52. Publishing House of the Hungarian Academy of Science, 1973. Citations: § 3, 8, 59, 62, and 111

[AK75] Rudolf Ahlswede and János Körner. Source coding with side information and a converse for degraded broadcast channels. *IEEE Trans. Inf. Theory*, 21(6):629-637, 1975. doi:10.1109/TIT.1975.1055469. Citations: § 111

[Ara02] PK Aravind. A simple demonstration of Bell's theorem involving two observers and no probabilities or inequalities. CoRR, abs/quant-ph/0206070, 2002. arXiv:quant-ph/0206070. Citations: § 59

[Ari09] Erdal Arikan. Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. *IEEE Trans. Inf. Theory*, 55(7):3051-3073, 2009. doi:10.1109/TIT.2009.2021379. Citations: § 1 and 5

[AS04] Alexander A. Ageev and Maxim Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. *J. Comb. Optim.*, 8(3):307-328, 2004. doi:10.1023/B:JOCO.0000038913.96607.c2. Citations: § 25 and 26

[BB98] Shraga I. Bross and Ian F. Blake. Upper bound for uniquely decodable codes in a binary input N-user adder channel. *IEEE Trans. Inf. Theory*, 44(1):334-340, 1998. doi:10.1109/18.651062. Citations: § 86
[BBBE71] Max Born, Hedwig Born, Irene Born, and Albert Einstein. *The Born-Einstein letters: correspondence between Albert Einstein and Max and Hedwig Born from 1916 to 1955*. Walker, 1971. Citations: § 2 and 6

[BBC+93] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K. Wootters. Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels. *Phys. Rev. Lett.*, 70:1895-1899, Mar 1993. doi:10.1103/PhysRevLett.70.1895. Citations: § 2, 7, and 59

[BBT05] Gilles Brassard, Anne Broadbent, and Alain Tapp. Quantum pseudo-telepathy. *Foundations of Physics*, 35(11):1877-1907, 2005. doi:10.1007/s10701-005-7353-4. Citations: § 59

[BCE+16] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors. *Handbook of Computational Social Choice*. Cambridge University Press, 2016. doi:10.1017/CBO9781107446984. Citations: § 35

[BCP+14] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. Bell nonlocality. *Rev. Mod. Phys.*, 86:419-478, Apr 2014. doi:10.1103/RevModPhys.86.419. Citations: § 3, 7, and 59

[Bel64] J. S. Bell. On the Einstein Podolsky Rosen paradox. *Physics Physique Fizika*, 1:195-200, Nov 1964. doi:10.1103/PhysicsPhysiqueFizika.1.195. Citations: § 2 and 6

[Ber73] Patrick P. Bergmans. Random coding theorem for broadcast channels with degraded components. *IEEE Trans. Inf. Theory*, 19(2):197-207, 1973. doi:10.1109/TIT.1973.1054980. Citations: § 111

[BF18] Siddharth Barman and Omar Fawzi. Algorithmic aspects of optimal channel coding. *IEEE Trans. Inf. Theory*, 64(2):1038-1045, 2018. doi:10.1109/TIT.2017.2696963. Citations: § 1, 3, 5, 7, 19, 20, 21, 22, 59, 70, 105, 111, 112, and 133

[BFF21] Siddharth Barman, Omar Fawzi, and Paul Fermé. Tight approximation guarantees for concave coverage problems. In Markus Bläser and Benjamin Monmege, editors, *38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference)*, volume 187 of LIPIcs, pages 9:1-9:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.STACS.2021.9. Citations: § 4 and 8

[BFGG20] Siddharth Barman, Omar Fawzi, Suprovat Ghoshal, and Emirhan Gürpinar. Tight approximation bounds for maximum multi-coverage. In Daniel Bienstock and Giacomo Zambelli, editors, *Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, London, UK, June 8-10, 2020, Proceedings*, volume 12125 of Lecture Notes in Computer Science, pages 66-77. Springer, 2020. doi:10.1007/978-3-030-45771-6\_6. Citations: § 1, 2, 6, 12, 22, 24, 25, 26, 29, 41, and 111

[BG96] Claude Berrou and Alain Glavieux. Near optimum error correcting coding and decoding: turbo-codes. *IEEE Trans. Commun.*, 44(10):1261-1271, 1996. doi:10.1109/26.539767. Citations: § 1 and 5

[BH84] Andrew D Barbour and Peter Hall. On the rate of Poisson convergence. *Mathematical Proceedings of the Cambridge Philosophical Society*, 95(3):473-480, 1984. doi:10.1017/S0305004100061806. Citations: § 49

[BLS17] Markus Brill, Jean-François Laslier, and Piotr Skowron. Multiwinner approval rules as apportionment methods. In Satinder P. Singh and Shaul Markovitch, editors, *Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA*, pages 414-420. AAAI Press, 2017. doi:10.1177/0951629818775518. Citations: § 23
[BN05] Liad Blumrosen and Noam Nisan. On the computational power of iterative auctions. In John Riedl, Michael J. Kearns, and Michael K. Reiter, editors, *Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), Vancouver, BC, Canada, June 5-8, 2005*, pages 29–43. ACM, 2005. doi:10.1145/1064009.1064013. Citations: § 112

[BSST99] Charles H Bennett, Peter W Shor, John A Smolin, and Ashish V Thapliyal. Entanglement-assisted classical capacity of noisy quantum channels. *Physical Review Letters*, 83(15):3081, 1999. doi:10.1103/PhysRevLett.83.3081. Citations: § 2, 7, and 59

[BT96] Steven J. Brams and Alan D. Taylor. Fair division - from cake-cutting to dispute resolution. Cambridge University Press, 1996. Citations: § 112

[BW92] Charles H. Bennett and Stephen J. Wiesner. Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. *Phys. Rev. Lett.*, 69:2881–2884, Nov 1992. doi:10.1103/PhysRevLett.69.2881. Citations: § 2 and 6

[Can17] Clément L Canonne. A short note on Poisson tail bounds. Retrieved from the website: http://www.cs.columbia.edu/~ccanonne, 2017. Citations: § 42

[CC84] Michele Conforti and Gérard Cornuéjols. Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. *Discret. Appl. Math.*, 7(3):251–274, 1984. doi:10.1016/0166-218X(84) 90003-9. Citations: § 24

[CCK$^{+}$17] Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From Gap-ETH to FPT-inapproximability: Clique, dominating set, and more. In Chris Umans, editor, *58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017*, pages 743–754. IEEE Computer Society, 2017. doi:10.1109/FOCS.2017.74. Citations: § 25 and 34

[CCPV11] Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. *SIAM J. Comput.*, 40(6):1740–1766, 2011. doi:10.1137/080733991. Citations: § 26

[CFN77] Gérard Cornuéjols, Marshall L Fisher, and George L Nemhauser. Exceptional paper-location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. *Management science*, 23(8):789–810, 1977. doi:10.1287/mnsc.23.8.789. Citations: § 21 and 23

[Cha77] Gregory J. Chaitin. Algorithmic information theory. *IBM J. Res. Dev.*, 21(4):350–359, 1977. doi:10.1147/rd.214.0350. Citations: § 1 and 5

[CHSH69] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed experiment to test local hidden-variable theories. *Phys. Rev. Lett.*, 23:880–884, Oct 1969. doi:10.1103/PhysRevLett.23.880. Citations: § 2, 3, 6, and 7

[Cir80] Boris S. Cirel'Son. Quantum generalizations of Bell's inequality. *Letters in Mathematical Physics*, 4(2):93–100, Mar 1980. doi:10.1007/BF00417500. Citations: § 2, 3, and 7

[CLMW10] Toby S. Cubitt, Debbie Leung, William Matthews, and Andreas Winter. Improving zero-error classical communication with entanglement. *Phys. Rev. Lett.*, 104:230503, Jun 2010. doi:10.1103/PhysRevLett.104.230503. Citations: § 2 and 7

[Cov72] Thomas M. Cover. Broadcast channels. *IEEE Trans. Inf. Theory*, 18(1):2–14, 1972. doi:10.1109/TIT.1972.1054727. Citations: § 3, 8, and 111

[Cov75] Thomas M. Cover. An achievable rate region for the broadcast channel. *IEEE Transactions on Information Theory*, 21(4):399–404, 1975. doi:10.1109/TIT.1975.1055418. Citations: § 111
[CPM19] Rahul Chandan, Dario Paccagnan, and Jason R. Marden. Optimal mechanisms for distributed resource-allocation. *CoRR*, abs/1911.07823, 2019. arXiv:1911.07823. Citations: § 23 and 38

[CRBT22] Michael X. Cao, Navneeth Ramakrishnan, Mario Berta, and Marco Tomamichel. Channel simulation: Finite blocklengths and broadcast channels. *CoRR*, abs/2212.11666, 2022. arXiv:2212.11666, doi:10.48550/arXiv.2212.11666. Citations: § 3 and 7

[CT01] Thomas M. Cover and Joy A. Thomas. *Elements of Information Theory*. Wiley, 2001. doi:10.1002/0471200611. Citations: § 35 and 62

[DMMS20] Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, and Krzysztof Sornat. Tight approximation for proportional approval voting. In Christian Bessiere, editor, *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020*, pages 276–282. ijcai.org, 2020. doi:10.24963/ijcai.2020/39. Citations: § 23, 24, 25, 37, 41, 51, and 55

[DR98] Devdatt P. Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. *Random Struct. Algorithms*, 13(2):99–124, 1998. doi:10.7146/brics.v3i25.20006. Citations: § 13

[DS06] Shahar Dobzinski and Michael Schapira. An improved approximation algorithm for combinatorial auctions with submodular bidders. In *Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006*, Miami, Florida, USA, January 22-26, 2006, pages 1064–1073. ACM Press, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109675. Citations: § 112, 134, and 135

[DV15] Shaddin Dughmi and Jan Vondrák. Limitations of randomized mechanisms for combinatorial auctions. *Games Econ. Behav.*, 92:370–400, 2015. doi:10.1016/j.geb.2014.01.007. Citations: § 21

[Eli57] Peter Elias. List decoding for noisy channels. *Technical Report*, 335, 1957. URL: https://dspace.mit.edu/bitstream/handle/1721.1/4484/RLE-TR-335-04734756.pdf. Citations: § 1, 5, 22, and 35

[EPR35] A. Einstein, B. Podolsky, and N. Rosen. Can quantum-mechanical description of physical reality be considered complete? *Phys. Rev.*, 47:777–780, May 1935. doi:10.1103/PhysRev.47.777. Citations: § 2 and 6

[Fei98] Uriel Feige. A threshold of $ln n$ for approximating set cover. *J. ACM*, 45(4):634–652, 1998. doi:10.1145/285055.285059. Citations: § 1, 5, 21, 25, and 29

[Fei02] Uriel Feige. Relations between average case complexity and approximation complexity. In John H. Reif, editor, *Proceedings on 34th Annual ACM Symposium on Theory of Computing*, May 19-21, 2002, Montréal, Québec, Canada, pages 534–543. ACM, 2002. doi:10.1145/509907.509985. Citations: § 70

[FF22] Omar Fawzi and Paul Fermé. Beating the sum-rate capacity of the binary adder channel with non-signaling correlations. In *IEEE International Symposium on Information Theory, ISIT 2022, Espoo, Finland, June 26 - July 1, 2022*, pages 2750–2755. IEEE, 2022. doi:10.1109/ISIT50566.2022.9834699. Citations: § 4 and 8

[FF23] Omar Fawzi and Paul Fermé. Multiple-access channel coding with non-signaling correlations. pages 1–1, 2023. doi:10.1109/TIT.2023.3301719. Citations: § 4 and 8

[FK14] Vitaly Feldman and Pravesh Kothari. Learning coverage functions and private release of marginals. In Maria-Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, *Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014*, volume 35 of *JMLR Workshop and Conference Proceedings*, pages 679–702. JMLR.org, 2014. URL: http://proceedings.mlr.press/v35/feldman14a.html. Citations: § 21
[FKP01] Uriel Feige, Guy Kortsarz, and David Peleg. The dense k-subgraph problem. Algorithmica, 29(3):410-421, 2001. doi:10.1007/s004530010050. Citations: § 70 and 111

[FW10] Manuel Fernández and Stuart Williams. Closed-form expression for the Poisson-binomial probability density function. IEEE Transactions on Aerospace and Electronic Systems, 46(2):803-817, 2010. doi:10.1109/TAES.2010.5461658. Citations: § 49

[Gal62] Robert G. Gallager. Low-density parity-check codes. IRE Trans. Inf. Theory, 8(1):21-28, 1962. doi:10.1109/TIT.1962.1057683. Citations: § 1 and 5

[Gal74] R.G. Gallager. Capacity and coding for degraded broadcast channels. Problemy Peredachi Informatsii, 10(3):3-14, 1974. Citations: § 111

[GJ79] M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Citations: § 126

[GK11] Abbas El Gamal and Young-Han Kim. Network Information Theory. Cambridge University Press, 2011. doi:10.1017/CBO9781139030687. Citations: § 15 and 16

[GM07] Bernd Gärtner and Jirí Matousek. Understanding and using linear programming. Universitext. Springer, 2007. doi:10.1007/978-3-540-30717-4. Citations: § 66, 81, and 120

[GN20] Amin Gohari and Chandra Nair. New outer bounds for the two-receiver broadcast channel. In IEEE International Symposium on Information Theory, ISIT 2020, Los Angeles, CA, USA, June 21-26, 2020, pages 1492-1497. IEEE, 2020. doi:10.1109/ISIT44484.2020.9174003. Citations: § 111

[GP80] Sergei Izrail'evich Gel'fand and Mark Semenovich Pinsker. Capacity of a broadcast channel with one deterministic component. Problemy Peredachi Informatsii, 16(1):24-34, 1980. Citations: § 111

[HDW08] Min-Hsiu Hsieh, Igor Devetak, and Andreas J. Winter. Entanglement-assisted capacity of quantum multiple-access channels. IEEE Trans. Inf. Theory, 54(7):3078-3090, 2008. doi:10.1109/TIT.2008.924726. Citations: § 60

[Hoc97] Dorit S. Hochbaum. Approximation algorithms for NP-hard problems. SIGACT News, 28(2):40-52, 1997. doi:10.1145/261342.571216. Citations: § 21

[Hoe63] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. doi:10.1080/01621459.1963.10500830. Citations: § 13

[Hol73] Alexander Semenovich Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii, 9(3):3-11, 1973. Citations: § 2 and 6

[Hop81] Grace Murray Hopper. The first bug. Annals of the History of Computing, 3(3):285-286, 1981. Citations: § 1 and 5

[JDP83] Kumar Joag-Dev and Frank Proschan. Negative association of random variables with applications. The Annals of Statistics, pages 286-295, 1983. doi:10.1214/aos/1176346079. Citations: § 12

[Jen06] Johan Ludwig William Valdemar Jensen. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta mathematica, 30(1):175-193, 1906. doi:10.1007/BF02418571. Citations: § 11

[JNV+20] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*=RE. CoRR, abs/2001.04383, 2020. URL: https://arxiv.org/abs/2001.04383, arXiv:2001.04383. Citations: § 60, 142, and 144

[Jr.78] E. J. Weldon Jr. Coding for a multiple-access channel. Inf. Control., 36(3):256-274, 1978. doi:10.1016/S0019-9958(78)90312-1. Citations: § 86
[Kho02] Subhash Khot. On the power of unique 2-prover 1-round games. In John H. Reif, editor, *Proceedings on 34th Annual ACM Symposium on Theory of Computing*, May 19-21, 2002, *Montréal, Québec, Canada*, pages 767-775. ACM, 2002. doi:10.1145/509907.510017.
Citations: § 2 and 6

[KL78] Tadao Kasami and Shu Lin. Bounds on the achievable rates of block coding for a memoryless multiple-access channel. *IEEE Trans. Inf. Theory*, 24(2):187-197, 1978. doi:10.1109/TIT.1978.1055860. Citations: § 86

[KLWY83] Tadao Kasami, Shu Lin, Victor K.-W. Wei, and Saburo Yamamura. Graph theoretic approaches to the code construction for the two-user multiple-access binary adder channel. *IEEE Trans. Inf. Theory*, 29(1):114-130, 1983. doi:10.1109/TIT.1983.1056614.
Citations: § 86 and 87

[LALS20] Felix Leditzky, Mohammad A Alhejji, Joshua Levin, and Graeme Smith. Playing games with multiple access channels. *Nature communications*, 11(1):1-5, 2020. doi:10.1038/s41467-020-15240-w.
Citations: § 3, 8, 59, 70, and 111

[Lia73] Henry Herng-Jiunn Liao. Multiple access channels (Ph.D. Thesis abstr.). *IEEE Trans. Inf. Theory*, 19(2):253, 1973. doi:10.1109/TIT.1973.1054960. Citations: § 3, 8, 59, 62, and 111

[Lin69] Bernt Lindström. Determination of two vectors from the sum. *Journal of Combinatorial Theory*, 6(4):402-407, 1969. doi:10.1016/S0021-9800(69)80038-4. Citations: § 86

[Man20] Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Shuchi Chawla, editor, *Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020*, pages 62-81. SIAM, 2020. doi:10.1137/1.9781611975994.5. Citations: § 24 and 34

[Mar77] Katalin Marton. The capacity region of deterministic broadcast channels. In *Trans. Int. Symp. Inform. Theory*, pages 243-248, 1977. Citations: § 111

[Mar79] Katalin Marton. A coding theorem for the discrete memoryless broadcast channel. *IEEE Trans. Inf. Theory*, 25(3):306-311, 1979. doi:10.1109/TIT.1979.1056046. Citations: § 111

[Mat12] William Matthews. A linear program for the finite block length converse of Polyanskiy-Poor-Verdú via nonsignaling codes. *IEEE Trans. Inf. Theory*, 58(12):7036-7044, 2012. doi:10.1109/TIT.2012.2210695. Citations: § 3, 7, 59, and 96

[Mer90] N David Mermin. Simple unified form for the major no-hidden-variables theorems. *Physical review letters*, 65(27):3373, 1990. doi:10.1103/PhysRevLett.65.3373. Citations: § 59

[MÖ05] M. Mattas and Patric R. J. Östergård. A new bound for the zero-error capacity region of the two-user binary adder channel. *IEEE Trans. Inf. Theory*, 51(9):3289-3291, 2005. doi:10.1109/TIT.2005.853309. Citations: § 86 and 87

[Mou03] Hervé Moulin. Fair division and collective welfare. MIT Press, 2003. Citations: § 112

[MSV08] Vahab S. Mirrokni, Michael Schapira, and Jan Vondrák. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In Lance Fortnow, John Riedl, and Tuomas Sandholm, editors, *Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008*, pages 70-77. ACM, 2008. doi:10.1145/1386790.1386805. Citations: § 112, 134, and 135

[Mur00] Robert A Murphey. Target-based weapon target assignment problems. In *Nonlinear assignment problems*, pages 39-53. Springer, 2000. doi:10.1007/978-1-4757-3155-2_3.
Citations: § 23 and 38
[MW08] Jason R. Marden and Adam Wierman. Distributed welfare games with applications to sensor coverage. In Proceedings of the 47th IEEE Conference on Decision and Control, CDC 2008, December 9-11, 2008, Cancún, Mexico, pages 1708-1713. IEEE, 2008. doi: 10.1109/CDC.2008.4738800. Citations: § 23

[ND20] Janis Nötzel and Stephen Diadamo. Entanglement-enabled communication for the internet of things. In Mohammad S. Obaidat, Kuei-Fang Hsiao, Petros Nicopolitidis, and Daniel Cascado Caballero, editors, International Conference on Computer, Information and Telecommunication Systems, CITS 2020, Hangzhou, China, October 5-7, 2020, pages 1-6. IEEE, 2020. doi:10.1109/CITS49457.2020.9232550. Citations: § 59

[NG07] Chandra Nair and Abbas El Gamal. An outer bound to the capacity region of the broadcast channel. IEEE Trans. Inf. Theory, 53(1):350-355, 2007. doi:10.1109/TIT.2006.887492. Citations: § 111

[Noe20] Janis Noetzel. Entanglement-enabled communication. IEEE J. Sel. Areas Inf. Theory, 1(2):401-415, 2020. doi:10.1109/jsait.2020.3017121. Citations: § 59

[NRTV07] Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007. doi:10.1017/CBO9780511800481. Citations: § 35 and 39

[OS15] Or Ordentlich and Ofer Shayevitz. A VC-dimension-based outer bound on the zero-error capacity of the binary adder channel. In IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, China, June 14-19, 2015, pages 2366-2370. IEEE, 2015. doi:10.1109/ISIT.2015.7282879. Citations: § 86

[PDB21] Uzi Pereg, Christian Deppe, and Holger Boche. Quantum broadcast channels with cooperating decoders: An information-theoretic perspective on quantum repeaters. Journal of Mathematical Physics, 62(6):062204, 06 2021. arXiv:2011.09233, doi:10.1063/5.0038083. Citations: § 111, 112, and 118

[PDB23] Uzi Pereg, Christian Deppe, and Holger Boche. The multiple-access channel with entangled transmitters. CoRR, abs/2303.10456, 2023. arXiv:2303.10456, doi:10.48550/arXiv.2303.10456. Citations: § 60

[Pee03] René Peeters. The maximum edge biclique problem is NP-complete. Discret. Appl. Math., 131(3):651-654, 2003. doi:10.1016/S0166-218X(03)00333-0. Citations: § 70

[Per90] Asher Peres. Incompatible results of quantum measurements. Physics Letters A, 151(3-4):107-108, 1990. doi:10.1016/0375-9601(90)90172-K. Citations: § 59

[Pin78] Mark Semenovich Pinsker. Capacity of noiseless broadcast channel. Problemy Peredachi Informatsii, 14(2):28-34, 1978. Citations: § 111

[PLM+11] R. Prevedel, Y. Lu, W. Matthews, R. Kaltenbaek, and K. J. Resch. Entanglement-enhanced classical communication over a noisy classical channel. Phys. Rev. Lett., 106:110505, Mar 2011. doi:10.1103/PhysRevLett.106.110505. Citations: § 2, 7, and 59

[PM18] Dario Paccagnan and Jason R Marden. Utility design for distributed resource allocation-part II: Applications to submodular, covering, and supermodular problems. CoRR, abs/1807.01343, 2018. arXiv:1807.01343. Citations: § 23, 37, 38, 39, and 40

[PPV10] Yury Polyanskiy, H. Vincent Poor, and Sergio Verdú. Channel coding rate in the finite blocklength regime. IEEE Trans. Inf. Theory, 56(5):2307-2359, 2010. doi:10.1109/TIT.2010.2043769. Citations: § 96 and 98

[PR94] Sandu Popescu and Daniel Rohrlich. Quantum nonlocality as an axiom. Foundations of Physics, 24(3):379-385, 1994. doi:10.1007/BF02058098. Citations: § 2, 3, and 7

[QS17] Yihui Quek and Peter W. Shor. Quantum and superquantum enhancements to two-sender, two-receiver channels. Phys. Rev. A, 95:052329, May 2017. doi:10.1103/PhysRevA.95.052329. Citations: § 3, 8, 59, and 111
[RU08] Thomas J. Richardson and Rüdiger L. Urbanke. *Modern Coding Theory*. Cambridge University Press, 2008. doi:10.1017/cbo9780511791338. Citations: § 1 and 5

[RWW06] Renato Renner, Stefan Wolf, and Jürg Wullschleger. The single-serving channel capacity. In *Proceedings 2006 IEEE International Symposium on Information Theory, ISIT 2006*, The Westin Seattle, Seattle, Washington, USA, July 9-14, 2006, pages 1424-1427. IEEE, 2006. doi:10.1109/ISIT.2006.262081. Citations: § 1 and 5

[Sat78] Hiroshi Sato. An outer bound to the capacity region of broadcast channels (corresp.). *IEEE Trans. Inf. Theory*, 24(3):374-377, 1978. doi:10.1109/TIT.1978.1055883. Citations: § 111

[SFL16] Piotr Skowron, Piotr Faliszewski, and Jérôme Lang. Finding a collective set of items: From proportional multirepresentation to group recommendation. *Artif. Intell.*, 241:191-216, 2016. doi:10.1016/j.artint.2016.09.003. Citations: § 23

[Sha48] Claude E. Shannon. A mathematical theory of communication. *Bell Syst. Tech. J.*, 27(3):379-423, 1948. doi:10.1002/j.1538-7305.1948.tb01338.x. Citations: § 1, 5, and 111

[Sha61] Claude E. Shannon. Two-way communication channels. In *Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics*, volume 4, pages 611-645. University of California Press, 1961. Citations: § 3 and 8

[SLSS22] Akshay Seshadri, Felix Leditzky, Vikesh Siddhu, and Graeme Smith. On the separation of correlation-assisted sum capacities of multiple access channels. In *IEEE International Symposium on Information Theory, ISIT 2022, Espoo, Finland, June 26 - July 1, 2022*, pages 2756-2761. IEEE, 2022. doi:10.1109/ISIT50566.2022.9834459. Citations: § 3, 8, 59, and 111

[SS07] Moshe Shaked and J George Shanthikumar. *Stochastic orders*. Springer Science & Business Media, 2007. doi:10.1007/978-0-387-34675-5. Citations: § 12

[SVW17] Maxim Sviridenko, Jan Vondrák, and Justin Ward. Optimal approximation for sub-modular and supermodular optimization with bounded curvature. *Math. Oper. Res.*, 42(4):1197-1218, 2017. doi:10.1287/moor.2016.0842. Citations: § 24, 39, 40, 41, and 47

[TBR16] Marco Tomamichel, Mario Berta, and Joseph M Renes. Quantum coding with finite resources. *Nature communications*, 7(1):11419, 2016. doi:10.1038/ncomms11419. Citations: § 1 and 5

[Tom12] Marco Tomamichel. *A framework for non-asymptotic quantum information theory*. PhD thesis, ETH Zürich, 2012. doi:10.48550/arXiv.1203.2142. Citations: § 1 and 5

[TT19] Wenpin Tang and Fengmin Tang. The Poisson binomial distribution-old & new. *CoRR*, abs/1908.10024, 2019. doi:10.1007/s41425-019-0024-9. Citations: § 49

[UL98] Rüdiger Urbanke and Quinn Li. The zero-error capacity region of the 2-user synchronous BAC is strictly smaller than its Shannon capacity region. In *1998 Information Theory Workshop (Cat. No. 98EX131)*, page 61. IEEE, 1998. doi:10.1109/ITW.1998.706434. Citations: § 86

[vdBvT85] P. A. B. M. Coebergh van den Braak and Henk C. A. van Tilborg. A family of good uniquely decodable code pairs for the two-access binary adder channel. *IEEE Trans. Inf. Theory*, 31(1):3-9, 1985. doi:10.1109/TIT.1985.1057004. Citations: § 86 and 87

[vdM75] Edward C. van der Meulen. Random coding theorems for the general discrete memoryless broadcast channel. *IEEE Trans. Inf. Theory*, 21(2):180-190, 1975. doi:10.1109/TIT.1975.1055347. Citations: § 111
[Von07] Jan Vondrák. Submodularity in Combinatorial Optimization. *Univerzita Karlova, Matematicko-Fyzikální Fakulta*, 2007. URL: https://dspace.cuni.cz/bitstream/handle/20.500.11956/13738/140038775.pdf. Citations: § 26, 28, and 39

[Von08] Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Cynthia Dwork, editor, *Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008*, pages 67–74. ACM, 2008. doi:10.1145/1374376.1374389. Citations: § 126 and 128

[vT78] Henk C. A. van Tilborg. An upper bound for codes in a two-access binary erasure channel (Corresp.). *IEEE Trans. Inf. Theory*, 24(1):112–116, 1978. doi:10.1109/TIT.1978.1055814. Citations: § 86

[Wil90] F.M.J. Willems. The maximal-error and average-error capacity region of the broadcast channel are identical: A direct proof. *Problems of Control and Information Theory*, 19(4):339–347, December 1990. URL: https://research.tue.nl/nl/publications/the-maximal-error-and-average-error-capacity-region-of-the-broadc. Citations: § 115

[Woz58] John M Wozencraft. List decoding. *Quarterly Progress Report*, 48:90–95, 1958. Citations: § 1, 5, 22, and 35

[YRB20] Jiyoung Yun, Ashutosh Rai, and Joonwoo Bae. Nonlocal network coding in interference channels. *Physical Review Letters*, 125(15):150502, 2020. doi:10.1103/PhysRevLett.125.150502. Citations: § 59

[YRB23] Jiyoung Yun, Ashutosh Rai, and Joonwoo Bae. Non-local and quantum advantages in network coding for multiple access channels. *CoRR*, abs/2304.10792, 2023. arXiv:2304.10792. Citations: § 59