# Approximation Algorithms for Channel Coding and Non-Signaling Correlations

Paul Fermé

► To cite this version:

Paul Fermé. Approximation Algorithms for Channel Coding and Non-Signaling Correlations. Information Theory [cs.IT]. ENS de Lyon, 2023. English. NNT: tel-04391153

HAL Id: tel-04391153

https://hal.science/tel-04391153

Submitted on 12 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
THÈSE
en vue de l'obtention du grade de Docteur, délivré par
l'École Normale Supérieure de Lyon

École Doctorale N°512
École Doctorale en Informatique et Mathématiques de Lyon

Discipline : Informatique

Soutenue publiquement le 29/11/2023, par :
Paul Fermé

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

Devant le jury composé de :

BERTA Mario, Professeur, RWTH Aachen University (Allemagne)

ROMASHCHENKO Andrei, Chargé de Recherche-HDR, LIRMM

GORCE Jean-Marie, Professeur des Universités, INSA Lyon

NEWMAN Alantha, Chargée de Recherche, Université Grenoble Alpes

FAWZI Omar, Directeur de Recherche, Inria et ENS de Lyon

Rapporteur

Rapporteur

Examinateur

Examinatrice

Directeur de thèse
<figure><img src="image_2.png" /></figure>
À ma mère,
à mon père.
Abstract

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 coding 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 \mathbb{N}^*} \frac{\mathbb{E}[\varphi(\mathrm{Poi}(x))]}{\varphi(\mathbb{E}[\mathrm{Poi}(x)])}$, which cannot be improved for sublinear $\varphi$ if $P \neq \mathrm{NP}$.

For multiple-access channels, we show that the coding problem cannot be approximated within any constant ratio under a 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 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 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 - e^{-1})^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.
# Résumé

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 \mathbb{N}^*} \frac{\mathbb{E}[\varphi(\text{Poi}(x))]}{\varphi(\mathbb{E}[\text{Poi}(x)])}$, qui ne peut être amélioré pour $\varphi$ sous-linéaire si $P \neq \text{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é n'est pas modifiée.

Pour les canaux de diffusion, lorsque l'on se limite aux canaux déterministes, nous fournissons une $(1 - e^{-1})^2$-approximation pour le problème du codage sans assistance, et nous montrons 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 montrons que nous ne pouvons pas obtenir un meilleur ratio d'approximation que $\Omega(\frac{1}{\sqrt{m}})$ pour le problème global du codage des canaux de diffusion, où $m$ est la taille de sortie du canal.
Remerciements

Je tiens tout d'abord à remercier mon directeur de thèse Omar Fawzi, qui m'a accompagné durant toute la durée de ma thèse et m'a gratifié de sa présence et de sa disponibilité tout au long de celle-ci.

Je tiens à remercier Mario Berta et Andrei Romashchenko d'avoir accepté de participer à mon jury de thèse en tant que rapporteurs, ainsi qu'à Jean-Marie Gorce et Alantha Newman en tant qu'examentateur et examinatrice.

Je tiens également à remercier Siddharth Barman pour les collaborations ainsi que pour les discussions autour des problèmes algorithmiques venant de l'économie.

Merci Stéphan et Pascal pour le temps passé tout au long de cette thèse autour de moments conviviaux et scientifiques. Un grand merci Subhayan pour la bonne humeur à toute épreuve, la compagnie dans l'effort et l'aide généreuse fournie durant toutes ces années. Merci Rémi pour ces débats endiablés qui ont rythmé les semaines et brisé tout risque de monotonie au fil des mois. Merci Peter pour toute l'aide scientifique et l'accueil chaleureux au début de ma thèse. Et merci Julien pour les pauses caféinées et cartonnées nécessaires à la recharge des batteries.

Merci Maïwenn de m'avoir convaincu de me lancer dans cette thèse malgré les hésitations initiales. Merci Lilian d'avoir été présent tout au long de la thèse, autour de restaurants, de musique, de cafés et débats partagés par delà nos laboratoires respectifs.

Un merci très spécial à Léo pour la décennie d'amitié et de soutien réciproque depuis notre rencontre à l'ENS de Lyon. Et un autre merci tout aussi particulier à Nils, pour la musique, pour l'amitié, et pour toutes les expériences partagées depuis à peu près aussi longtemps.

Enfin, merci Claire de m'accompagner dans ce marathon depuis ses débuts et par-delà les épreuves rencontrées en chemin.
<figure><img src="image_3.png" /></figure>
# Contents

Abstract iii

Contents vii

List of Symbols xi

1 Introduction 1

2 Background 11

2.1 Probability Theory 11

2.1.1 Usual Distributions and Properties 11

2.1.2 Negatively Associated Random Variables 12

2.1.3 Non-Signaling Probability Distributions 13

2.2 Information Theory 14

2.2.1 Information Quantities 14

2.2.2 Typical Sets 15

2.2.3 Channels 17

2.2.4 Capacity Regions 18

2.3 Channel Coding for Point-to-Point Channels 19

3 Tight Approximation Guarantees for Concave Coverage Problems 21

3.1 Approximation Algorithm for $\phi$-MAXCOVERAGE 25

3.1.1 Generalization to Matroid Constraints 27

3.2 Hardness of Approximation for $\phi$-MAXCOVERAGE 28

3.2.1 Partitioning System 29

3.2.2 The Reduction 30

3.2.3 Further Hardness Under Gap-ETH 34

3.3 Applications 35

3.3.1 Generalized List-Decoding 35

3.3.2 Multiwinner Elections 36

3.3.3 Resource Allocation in Multi-Agent Systems 37

3.3.4 Vehicle-Target Assignment 38

3.3.5 Welfare Maximization for $\phi$-Coverage 39

3.4 Conclusion 40
<table><tbody><tr><td>3.5 Appendix</td><td>42</td></tr><tr><td>3.5.1 General Properties</td><td>42</td></tr><tr><td>3.5.2 Calculations of α<sub>ϕ</sub></td><td>53</td></tr><tr><td>3.5.3 NP-hardness of δ, h-ARYGAPLABELCOVER</td><td>55</td></tr><tr><td>3.5.4 Proof of Existence of Partitioning Systems</td><td>56</td></tr><tr><td>3.5.5 Proof of Theorem 3.15</td><td>57</td></tr><tr><td><b>4 Multiple-Access Channel Coding With Non-Signaling Correlations</b></td><td><b>59</b></td></tr><tr><td>4.1 Multiple-Access Channels Capacity Regions</td><td>61</td></tr><tr><td>4.1.1 Classical Capacities</td><td>61</td></tr><tr><td>4.1.2 Non-Signaling Assisted Capacities</td><td>64</td></tr><tr><td>4.2 Hardness of Approximation for Multiple-Access Channel Coding</td><td>70</td></tr><tr><td>4.3 Properties of Non-Signaling Assisted Codes</td><td>73</td></tr><tr><td>4.3.1 Symmetrization</td><td>73</td></tr><tr><td>4.3.2 Properties of S<sup>NS</sup>(W, k<sub>1</sub>, k<sub>2</sub>), C<sup>NS</sup>(W) and C<sub>0</sub><sup>NS</sup>(W)</td><td>75</td></tr><tr><td>4.3.3 Linear Program With Reduced Size for Structured Channels</td><td>80</td></tr><tr><td>4.4 Non-Signaling Achievability Bounds</td><td>85</td></tr><tr><td>4.4.1 Zero-Error Non-Signaling Assisted Achievable Rate Pairs</td><td>85</td></tr><tr><td>4.4.2 Non-Signaling Assisted Achievable Rate Pairs With Non-Zero Error</td><td>87</td></tr><tr><td>4.5 Relaxed Non-Signaling Assisted Capacity Region and Outer Bounds</td><td>90</td></tr><tr><td>4.5.1 Outer Bound Part of Theorem 4.25</td><td>96</td></tr><tr><td>4.5.2 Achievability Part of Theorem 4.25</td><td>102</td></tr><tr><td>4.6 Independent Non-Signaling Assisted Capacity Region</td><td>105</td></tr><tr><td>4.7 Conclusion</td><td>108</td></tr><tr><td><b>5 Broadcast Channel Coding With Non-Signaling Correlations</b></td><td><b>111</b></td></tr><tr><td>5.1 Broadcast Channel Coding</td><td>113</td></tr><tr><td>5.1.1 Broadcast Channels</td><td>113</td></tr><tr><td>5.1.2 The Sum Success Probability S<sub>sum</sub>(W, k<sub>1</sub>, k<sub>2</sub>)</td><td>113</td></tr><tr><td>5.1.3 The Joint Success Probability S(W, k<sub>1</sub>, k<sub>2</sub>)</td><td>115</td></tr><tr><td>5.2 Non-Signaling Assistance</td><td>116</td></tr><tr><td>5.2.1 Non-Signaling Assistance Between Decoders</td><td>116</td></tr><tr><td>5.2.2 Full Non-Signaling Assistance</td><td>119</td></tr><tr><td>5.3 Approximation Algorithm for Deterministic Broadcast Channel Coding</td><td>123</td></tr><tr><td>5.3.1 Reformulation as a Bipartite Graph Problem</td><td>124</td></tr><tr><td>5.3.2 Approximation Algorithm for DENSESTQUOTIENTGRAPH</td><td>126</td></tr><tr><td>5.3.3 Non-Signaling Assisted Capacity Region for Deterministic Channels</td><td>128</td></tr><tr><td>5.4 Hardness of Approximation for Broadcast Channel Coding</td><td>133</td></tr><tr><td>5.4.1 Social Welfare Reformulation</td><td>134</td></tr><tr><td>5.4.2 Value Query Hardness</td><td>134</td></tr><tr><td>5.4.3 Limitations of the Model</td><td>140</td></tr><tr><td>5.5 Conclusion</td><td>140</td></tr><tr><td><b>6 Conclusion</b></td><td><b>141</b></td></tr><tr><td><b>Bibliography</b></td><td><b>145</b></td></tr></tbody></table>
# Table des matières

<table><tr><td>Résumé</td><td>iv</td></tr><tr><td>Remerciements</td><td>v</td></tr><tr><td>Table des matières</td><td>x</td></tr><tr><td>Liste des symboles et abréviations</td><td>xi</td></tr><tr><td>1 Introduction</td><td>5</td></tr><tr><td>2 Préliminaires</td><td>11</td></tr><tr><td>2.1 Probabilités</td><td>11</td></tr><tr><td>2.2 Théorie de l'information</td><td>14</td></tr><tr><td>2.3 Problème du codage pour les canaux un-à-un</td><td>19</td></tr><tr><td>3 Strictes garanties d'approximation pour des problèmes de couverture concaves</td><td>21</td></tr><tr><td>3.1 Algorithme d'approximation pour ϕ-MAXCOVERAGE</td><td>25</td></tr><tr><td>3.2 Difficulté d'approximation pour ϕ-MAXCOVERAGE</td><td>28</td></tr><tr><td>3.3 Applications</td><td>35</td></tr><tr><td>3.4 Conclusion</td><td>40</td></tr><tr><td>4 Problème du codage pour les canaux à accès multiple et corrélations non-signalantes</td><td>59</td></tr><tr><td>4.1 Zones de capacité pour les canaux à accès multiple</td><td>61</td></tr><tr><td>4.2 Difficulté d'approximation pour le problème du codage pour les canaux à accès multiple</td><td>70</td></tr></table>
<table><tr><td>4.3</td><td>Propriétés des codes avec assistance non-signalante</td><td>73</td></tr><tr><td>4.4</td><td>Bornes sur les taux atteignables avec assistance non-signalante</td><td>85</td></tr><tr><td>4.5</td><td>Zone de capacité avec assistance non-signalante relaxée et bornes extérieures</td><td>90</td></tr><tr><td>4.6</td><td>Zone de capacité avec assistance non-signalante indépendante</td><td>105</td></tr><tr><td>4.7</td><td>Conclusion</td><td>108</td></tr></table>

5 **Problème du codage pour les canaux de diffusion et corrélations non-signalantes** 111

<table><tr><td>5.1</td><td>Problème du codage pour les canaux de diffusion</td><td>113</td></tr><tr><td>5.2</td><td>Assistance non-signalante</td><td>116</td></tr><tr><td>5.3</td><td>Algorithme d'approximation pour le problème du codage pour les canaux de diffusion déterministes</td><td>123</td></tr><tr><td>5.4</td><td>Difficulté d'approximation pour le problème du codage pour les canaux de diffusion</td><td>133</td></tr><tr><td>5.5</td><td>Conclusion</td><td>140</td></tr></table>

6 **Conclusion** 143

**Bibliographie** 153
# List of Symbols

## GENERAL NOTATIONS

N the set of nonnegative integers

R the set of real numbers

[k] the set of integers from 1 to k, i.e. {1, ..., k}

$\mathfrak{S}_k$ the set of permutations over [k]

$(x, y)$ the set of real numbers $z$ such that $x < z < y$

$k, \ell, n, m, \dots$ nonnegative integers

$x, y, z, \dots$ real numbers

$p, q, \dots$ real numbers between 0 and 1

$\lfloor x \rfloor / \lfloor x \rfloor$ the ceiling/floor of $x$

$\log(x)$ the binary logarithm of $x$

$e^x / \exp(x)$ the exponential of $x$

$\mathbb{1}_A$ the truth value of the statement $A$

$k!$ the factorial of $k$

($\binom{n}{k}$) the binomial coefficient of parameters $n$ and $k$

## COMPLEXITY

P the class of problems decidable in polynomial time

NP the class of problems decidable in nondeterministic polynomial time

$O(f(n))$ a function at most of the order of $f(n)$ when $n$ tends to infinity

$\Omega(f(n))$ a function at least of the order of $f(n)$ when $n$ tends to infinity

$\Theta(f(n))$ a function of the order of $f(n)$ when $n$ tends to infinity

$o(f(n))$ a function dominated by $f(n)$ when $n$ tends to infinity

## GRAPHS

$G = (V, E)$ an undirected graph with vertices in $V$ and edges in $E$

$\deg_G(v)$ the degree of $v$ in $G$, i.e. the number of edges connected to $v$

## GROUPS

$G$ a group

$g$ an element of the group $G$

$\mathcal{X}, \mathcal{Y}, \mathcal{Z}, \dots$ sets where $G$ acts

$x, y, z, \dots$ elements of $\mathcal{X}, \mathcal{Y}, \mathcal{Z}, \dots$

$g \cdot x$ the action of $g$ on $x$

$\mathcal{O}_G(\mathcal{X})$ the set of orbits of $\mathcal{X}$ under the action of $G$
PROBABILITY

$\mathcal{X}, \mathcal{Y}, \mathcal{Z}, \dots$ finite sets

$X, Y, Z, \dots$ random variables over $\mathcal{X}, \mathcal{Y}, \mathcal{Z}, \dots$

$P_X, P_Y, P_Z, \dots$ the probability distributions of $X, Y, Z, \dots$

$\mathbb{P}(E)$ the probability of the event $E$

$\mathbb{E}[X]$ the expectation of $X$

$\sigma_X^2$ the variance of $X$

$\text{Ber}(p)$ the Bernoulli distribution of parameter $p$

$\text{Bin}(n, p)$ the binomial distribution of parameters $n, p$

$\text{Poi}(\lambda)$ the Poisson distribution of parameter $\lambda$

INFORMATION THEORY

$W$ a channel, possibly with multiple inputs or multiple outputs

$W \otimes W'$ the tensor product of the channels $W$ and $W'$

$W^{\otimes n}$ the $n$th tensor product of $W$

$C[S](W)$ the capacity region of $W$ for a success probability $S$

$C_0[S](W)$ the zero-error capacity region of $W$ for a success probability $S$

$x^n, y^n, z^n, \dots$ words in $\mathcal{X}^n, \mathcal{Y}^n, \mathcal{Z}^n, \dots$

$x_i, y_i, z_i, \dots$ the $i$th letter of $x^n, y^n, z^n, \dots$

$x_{-i}, y_{-i}, z_{-i}, \dots$ the words $x^n, y^n, z^n, \dots$ without their $i$th letter

$\mathcal{T}_{\varepsilon}^n(X)$ the set of $\varepsilon$-typical words of $n$ letters following $X$

$H(X)$ the entropy of $X$

$H(X|Y)$ the conditional entropy of $X$ given $Y$

$I(X : Y)$ the mutual information of $X$ and $Y$

$I(X : Y|Z)$ the conditional mutual information of $X$ and $Y$ given $Z$

$X \to Y \to Z$ a Markov chain
CHAPTER 1

Introduction

With the growing number of connected devices and the explosion in the amount of ex-
changed data, the need for efficient and reliable communication has never been as critical
as in today's world. Noise, coming from physical imperfection, signal interference, or even
*lepidopterans* [Hop81], is one of the major hurdles to overcome.

The Theory of Information established by Shannon in his seminal work [Sha48] provides clear and definite answers to the amount of data that can be transmitted through noisy point-to-point channels. The asymptotic rate at which information can be sent through multiple independent copies of a channel is fully characterized by a mathematical quantity called *capacity*. Although one cannot hope to surpass this fundamental limit, developing codes achieving the channel's capacity is not a simple task in practice, as the code construction by Shannon was only probabilistic and the decoding is inefficient as a function of the number of copies of the channel.

Nonetheless, restricting the study to binary symmetric channels, the research in error-
correcting codes led to capacity-approaching solutions with efficient encoding and decoding
procedures, such as low-density parity-check codes [Gal62], turbo codes [BG96] or more
recently polar codes [Ari09]; see [RU08] for a general review on error-correcting codes.

However, in some settings, it cannot be assumed that the channel copies are independent.
The field of one-shot information theory [RWW06, Tom12, TBR16] addresses this problem,
studying information theoretical quantities defined for a unique copy of an arbitrary channel.
Another approach, developed by Barman and Fawzi in [BF18], focuses on the algorithmic
aspects of coding for a single copy of a channel. The objective shifts to maximizing the
probability of successfully transmitting a message through that channel over all possible
encoders and decoders, known as the channel coding problem. As this algorithmic task
is NP-hard, they proposed a polynomial-time approximation algorithm achieving a ratio
of $1 - e^{-1}$, which cannot be increased if P ≠ NP thanks to a connection to the maximum
coverage problem [Fei98]. Note that this approach differs from algorithmic information
theory [Cha77], where information is defined using Turing machines rather than probability
theory.

Following this work, the *l*-list-decoding task [Eli57, Woz58], where the decoder is only asked to output a list of *l* possible guesses instead of giving the right input message, was studied from an algorithmic point of view in [BFGG20]. Similarly, they developed a (1 - (l^l e^-l) / l!)-approximation algorithm running in polynomial time, and proved that this
ratio cannot be increased under the unique games conjecture [Kho02]. More generally, a larger class of combinatorial optimization problems, called maximum *l*-multi-coverage, falls in the analysis of [BFGG20].

A natural extension of the maximum *l*-multi-coverage problem 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$, for a general nondecreasing concave function $\varphi$; the maximum *l*-multi-coverage problem is retrieved by taking $\varphi(x) := \min(x, l)$. In terms of channel coding interpretation, this corresponds to what we call $\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*. This problem will be the first subject of study of the thesis.

Shaking the physical foundations of the world at the beginning of the twentieth century, the rise of quantum mechanics has revolutionized the comprehension of nature at atomic and subatomic scale. One of its most intriguing characteristics is the notion of *entanglement*. Two entangled particles have the particularity of being correlated, even when spread apart, in a way that cannot be explained by non-quantum physics laws.

Einstein, Podolsky and Rosen [EPR35] first discovered that phenomenon, which implied either that the quantum-mechanical description of physical reality was not complete or that two incompatible physical quantities did not have simultaneously a concrete value. Surprisingly and contrary to the original goal of what has become known as the Einstein-Podolsky-Rosen paradox [EPR35], it is the latter that describes correctly the atomic and subatomic physical reality.

Bell showed in [Bel64] that no hidden-variable theory, where we could associate unknown local variables to each of the entangled particles, would be enough to explain their correlation when spread apart. This *nonlocal* nature of quantum physics is in contradiction with the usual principle of locality of classical physics, which states that any object can be influenced only by its immediate surroundings. The results in [Bel64] were generalized into the so-called CHSH inequality [CHSH69], which if violated, imply that a hidden-variable theory cannot explain the correlations between the particles. These inequalities violations were practically realized by Aspect et al. [ADR82], which finally proved the nonlocal nature of quantum physics.

Another particularity of quantum mechanics is that any measurement of physical properties of a quantum system actually disturbs it. Furthermore, in the case of entangled particles, measuring one of the particles will also affect the other. This *spooky action at a distance*, as stated by Einstein [BBBE71], does not violate special relativity, as one cannot actually transmit information through that process.

However, entanglement can be used to enhance communication. A qubit, the quantum basic unit of information, cannot by itself convey more than one bit of information [Hol73]. However, Bennett and Wiesner showed in [BW92] that if quantum entanglement is shared between the parties, in the form of what is called an EPR pair, then one can actually transmit two bits of information using only one qubit. This is known today as superdense coding. For point-to-point (classical) channels, quantum entanglement shared between the sender and the receiver can increase the optimal success probability of channel coding [CLMW10, PLM$^{+}$11], although it does not increase the channel capacity [BBC$^{+}$93, BSST99]. One can also abstract quantum entanglement into *non-signaling* correlations [Cir80, PR94].
In order to understand those, it is useful to look at the game interpretation of the previously mentioned CHSH inequality. We consider a two-player game with Alice and Bob. A referee gives a uniformly random bit $x$ (resp. $y$) to Alice (resp. Bob), and their common goal is to output respectively bits $a$ and $b$ such that $a \oplus b = x \wedge y$ without communicating, where $\oplus$ denotes the exclusive disjunction. It is easy to see that no strategy can lead to a better success probability than $\frac{3}{4}$, even assuming that hidden variables are shared between the players. However, as shown in [CHSH69], if Alice and Bob share an entangled EPR pair, they can apply well chosen measurements and achieve a success probability of $\cos^2(\frac{\pi}{8}) \approx 0.85$, which in fact cannot be outperformed [Cir80]. Note that the correlation $P(ab|xy)$ describing the result of this quantum strategy confirms that no information is transmitted using quantum entanglement. Indeed, one can show that the marginal from a player is independent of the other player's input, that is to say that $\sum_b P(ab|xy) = \sum_b P(ab|xy')$ and $\sum_a P(ab|xy) = \sum_a P(ab|x'y)$ for all $a, b, x, y, x', y'$. Non-signaling correlations are defined as the set of all joint distributions $P(ab|xy)$ that satisfy the previous equalities. They naturally include quantum strategies, but are in fact stronger, as one can even achieve a success probability of 1 for the CHSH game using a general non-signaling strategy, simply by defining $P(ab|xy) := \frac{1}{2}$ if $a \oplus b = x \wedge y$, and $P(ab|xy) := 0$ otherwise [PR94].

General non-signaling correlations are not representing physical reality, as they imply stronger nonlocal behaviors than those occurring within quantum mechanics. However, they present a strong theoretical interest. Notably, the description of the set of non-signaling correlations is much simpler than with quantum ones, as they are characterized by simple linear constraints; see [BCP$^{+}$14] for a general review on nonlocality.

The approximation algorithm for the channel coding problem in [BF18] relies in fact on non-signaling assisted codes. As finding the best non-signaling assisted code for a channel is a linear program, it can be solved exactly in polynomial time. They have developed a strategy to transform that non-signaling assisted code into a classical one, losing at most a factor $1 - e^{-1}$ in the success probability. A more precise statement of this strategy actually implies that the capacity regions with or without non-signaling assistance are the same, retrieving back a result by [Mat12]. It should also be noted that non-signaling assistance does not change the capacity region of the reverse task of channel simulation [CRBT22]. This unexpected link between approximation algorithms for the channel coding problem and non-signaling correlations is the main motivation of the rest of the thesis. Specifically, we will develop these analysis in the main network communication scenarios.

Network information theory, which aims at understanding communication over multiple-sender multiple-receiver channels, was first studied by Shannon in the particular case of two-way channels [Sha61] (known today as interference channels). Later, Cover [Cov72] introduced broadcast channels, with multiple receivers but a single sender. Ahlswede [Ahl73] and independently Liao [Lia73] studied the reverse scenario of multiple-access channels, with multiple senders but a single receiver. These more complex channels allow a better modelization of real-life interconnected communication.

Contrary to the point-to-point setting, nonlocality can increase the capacity of network channels. Quek and Shor showed in [QS17] the existence of two-sender two-receiver interference channels with gaps between their classical, quantum-entanglement assisted and non-signaling assisted capacity regions. Following this result, Leditzky et al. [LALS20, SLSS22] showed that quantum entanglement shared between the two senders of a multiple-access channel can strictly enlarge its capacity region.
We will address the coding problem for both multiple-access channels and broadcast channels. We will study the impact of non-signaling correlations on their capacities, as well as their links to approximation algorithms of the related coding problems.

**Contributions** In Chapter 3 (based on [BFF21]), we consider the following generalization of the maximum $l$-multi-coverage problem depending on a concave, nondecreasing function $\varphi$: given subsets $T_1, \dots, T_m$ of a universe $[n]$, positive weights $w_a$ on the universe $[n]$ and an integer $k$, the objective is to find a subset $S \subseteq [m]$ of size $k$ that maximizes $C^\varphi(S) := \sum_{a \in [n]} w_a \varphi(|S|_a)$, where $|S|_a := |\{i \in S : a \in T_i\}|$; the maximum $l$-multi-coverage problem is retrieved by taking $\varphi(x) := \min(x, l)$. For any such $\varphi$, we provide an efficient algorithm that achieves an approximation ratio equal to the Poisson concavity ratio of $\varphi$, defined by $\alpha_\varphi := \min_{x \in \mathbb{N}^*} \frac{\mathbb{E}[\varphi(\mathrm{Poi}(x))]}{\varphi(\mathbb{E}[\mathrm{Poi}(x)])}$. Complementing this approximation guarantee, we establish a matching NP-hardness result when $\varphi$ grows in a sublinear way. 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 obtain 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. Our result goes beyond this particular setting and we illustrate it with applications to distributed resource allocation problems, welfare maximization problems and approval-based voting for general rules.

In Chapter 4 (based on [FF22, FF23]), we address the problem of coding for multiple-access channels. We first show that it cannot be approximated in polynomial time within any constant ratio, under a complexity hypothesis on random $k$-SAT formulas. Then, we study the influence of non-signaling correlations between parties. We develop a linear program computing the optimal success probability for coding over $n$ copies of a multiple-access channel $W$ with size growing polynomially in $n$. Solving this linear program allows us to achieve inner bounds for multiple-access channels. Applying this method to the binary adder channel, we show that using non-signaling assistance, the sum-rate $\frac{\log_2(72)}{4} \approx 1.5425$ can be reached even with zero error, which beats the maximum sum-rate capacity of 1.5 in the unassisted case. For noisy channels, where the zero-error non-signaling assisted capacity region is trivial, we can use concatenated codes to obtain achievable points in the capacity region. Applied to a noisy version of the binary adder channel, we show that non-signaling assistance still improves the sum-rate capacity. Complementing these achievability results, we give an outer bound on the non-signaling assisted capacity region that has the same expression as the unassisted region except that the channel inputs are not required to be independent. Finally, we show that the capacity region with non-signaling assistance shared only between each sender and the receiver independently is the same as without assistance.

In Chapter 5, we address the problem of coding for 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 $\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.
Introduction

Avec le nombre croissant d'appareils connectés et l'explosion du volume de données échan-
gées, le besoin de communication efficace et fiable n'a jamais été aussi critique que dans
le monde d'aujourd'hui. Le bruit, qui provient d'imperfections physiques, d'interférences
entre les signaux ou même de *lépidoptères* [Hop81], est l'un des principaux obstacles à
surmonter.

La théorie de l'information établie par Shannon dans son ouvrage fondateur [Sha48] apporte
des réponses claires et précises à la quantité de données pouvant être transmises par des
canaux point à point bruités. Le taux asymptotique auquel les informations peuvent être
envoyées par de multiples copies indépendantes d'un canal est entièrement caractérisé par
une quantité mathématique appelée *capacité*. Bien que l'on ne puisse espérer dépasser cette
limite fondamentale, le développement de codes permettant d'atteindre la capacité du canal
n'est pas une tâche aisée en pratique, car la construction du code par Shannon n'était que
probabiliste et le décodage est inefficace en fonction du nombre de copies du canal.

Néanmoins, en limitant l'étude aux canaux symétriques binaires, la recherche sur les codes correcteurs d'erreurs a conduit à des solutions approchant la capacité avec des procédures de codage et de décodage efficaces, telles que les codes de contrôle de parité à faible densité [Gal62], les codes turbo [BG96] ou, plus récemment, les codes polaires [Ari09]; voir [RU08] pour une revue générale des codes correcteurs d'erreurs.

Toutefois, dans certains contextes, on ne peut pas supposer que les copies du canal sont
indépendantes. Le domaine de la théorie de l'information à un coup [RWW06, Tom12,
TBR16] aborde ce problème, en étudiant les quantités de la théorie de l'information définies
pour une copie unique d'un canal arbitraire. Une autre approche, développée par Barman
et Fawzi dans [BF18], se concentre sur les aspects algorithmiques du codage pour une
copie unique d'un canal. L'objectif consiste alors à maximiser la probabilité de transmettre
avec succès un message par ce canal pour tous les codeurs et décodeurs possibles, ce que
l'on appelle problème du codage de canal. Cette tâche algorithmique étant NP-difficile,
ils ont proposé un algorithme d'approximation en temps polynomial atteignant un ratio
de $1 - e^{-1}$, qui ne peut être augmenté si $P \neq NP$ grâce à un lien avec le problème de la
couverture maximale [Fei98]. Il convient de noter que cette approche diffère de la théorie
algorithmique de l'information [Cha77], où l'information est définie à l'aide de machines
de Turing plutôt qu'avec la théorie des probabilités.

Suite à ces travaux, le problème du décodage de listes de paramètre $\ell$ [Eli57, Woz58], où l'on
demande au décodeur de produire une liste de $\ell$ suppositions possibles au lieu de donner
le bon message d'entrée, a été étudié d'un point de vue algorithmique dans [BFGG20]. De
même, ils ont développé un algorithme d'approximation de ratio $1 - \frac{\ell^\ell e^{-\ell}}{\ell!}$ fonctionnant en
temps polynomial, et ont prouvé que ce ratio ne peut pas être augmenté sous l'hypothèse
de la conjecture des jeux uniques [Kho02]. Plus généralement, une classe plus large de
problèmes d'optimisation combinatoire, appelée couverture multiple maximale de paramètre
$\ell$, relève de l'analyse de [BFGG20].

Une extension naturelle du problème de couverture multiple maximale de paramètre $\ell$ consiste à maximiser la quantité $\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 ; le problème de couverture multiple maximale de paramètre $\ell$ est retrouvé en prenant $\varphi(x) := \min(x, \ell)$. En termes d'interprétation du codage de canal, cela correspond à ce que nous appelons le 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écodage correct d'une liste de suppositions de taille variable $\ell$. Ce problème sera le premier sujet d'étude de la thèse.

Au début du vingtième siècle, la mécanique quantique a ébranlé les fondements physiques du monde et révolutionné la compréhension de la nature à l'échelle atomique et subatomique. L'une de ses caractéristiques les plus fascinantes est la notion d'intrication. Deux particules intriquées ont la particularité d'être corrélées, même lorsqu'elles sont éloignées l'une de l'autre, d'une manière qui ne peut être expliquée par les lois de la physique non quantique.

Einstein, Podolsky et Rosen [EPR35] ont été les premiers à découvrir ce phénomène, qui impliquait soit que la description de la réalité physique par la mécanique quantique n'était pas complète, soit que deux grandeurs physiques incompatibles n'avaient pas simultanément une valeur concrète. De manière surprenante et contrairement à l'objectif initial de ce qui est devenu le paradoxe d'Einstein-Podolsky-Rosen [EPR35], c'est ce dernier qui décrit correctement la réalité physique atomique et subatomique.

Bell a montré dans [Bel64] qu'aucune théorie des variables cachées, où l'on pourrait associer des variables locales inconnues à chacune des particules intriquées, ne suffirait à expliquer leur corrélation lorsqu'elles sont éloignées l'une de l'autre. Cette nature non locale de la physique quantique est en contradiction avec le principe de localité de la physique classique, qui stipule que tout objet ne peut être influencé que par son environnement immédiat. Les résultats de [Bel64] ont été généralisés dans ce que l'on appelle les inégalités CHSH [CHSH69], qui, si elles sont violées, impliquent qu'une théorie des variables cachées ne peut pas expliquer les corrélations entre les particules. Les violations de ces inégalités ont été pratiquement réalisées par Aspect et al. [ADR82], ce qui a finalement prouvé la nature non locale de la physique quantique.

Une autre particularité de la mécanique quantique est que toute mesure des propriétés physiques d'un système quantique le perturbe. En outre, dans le cas de particules intriquées, la mesure de l'une des particules affectera également l'autre. Cette action étrange à distance, comme l'a décrite Einstein [BBBE71], ne viole pas la relativité restreinte, car il est impossible de transmettre des informations par ce biais.

Cependant, l'intrication peut être utilisée pour améliorer la communication. Un qubit, l'unité quantique de base de l'information, ne peut à lui seul transmettre plus d'un bit d'information [Hol73]. Cependant, Bennett et Wiesner ont montré dans [BW92] que si
l'intrication quantique est partagée entre les parties, sous la forme de ce que l'on appelle
une paire EPR, il est possible de transmettre deux bits d'information en utilisant un seul
qubit. C'est ce que l'on appelle aujourd'hui le codage superdense. Pour les canaux point
à point (classiques), l'intrication quantique partagée entre l'émetteur et le récepteur peut
augmenter la probabilité de succès optimale du codage de canal [CLMW10, PLM<sup>+</sup>11], bien
qu'elle n'augmente pas la capacité du canal [BBC<sup>+</sup>93, BSST99].

On peut également abstraire l'intrication quantique en corrélations *non-signalantes* [Cir80, PR94]. Afin de comprendre ces corrélations, il est utile d'examiner l'interprétation de l'inégalité CHSH mentionnée précédemment sous forme de jeu. Nous considérons un jeu à deux joueurs avec Alice et Bob. Un arbitre donne un bit uniformément aléatoire *x* (resp. *y*) à Alice (resp. Bob), et leur but commun est de choisir respectivement les bits *a* et *b* tels que *a* ⊕ *b* = *x* ∧ *y* sans communiquer, où ⊕ dénote la disjonction exclusive. Il est facile de voir qu'aucune stratégie ne peut conduire à une meilleure probabilité de succès que 3/4, même en supposant que des variables cachées sont partagées entre les joueurs. Cependant, comme le montre [CHSH69], si Alice et Bob partagent une paire EPR intriquée, ils peuvent appliquer des mesures bien choisies et atteindre une probabilité de succès de cos²(π/8) ≈ 0.85, ce qui en fait ne peut pas être surpassé [Cir80]. Notons que la corrélation P(ab|xy) décrivant le résultat de cette stratégie quantique confirme qu'aucune information n'est transmise à l'aide de l'intrication quantique. En effet, on peut montrer que la marginale d'un joueur est indépendante de l'entrée de l'autre joueur, c'est-à-dire que $\sum_b P(ab|xy) = \sum_b P(ab|xy')$ et $\sum_a P(ab|xy) = \sum_a P(ab|x'y)$ pour tous a, b, x, y, x', y'. Les corrélations non-signalantes sont définies comme l'ensemble des distributions conjointes P(ab|xy) qui satisfont les égalités précédentes. Elles incluent naturellement les stratégies quantiques, mais sont en fait plus fortes, car on peut même obtenir une probabilité de succès de 1 pour le jeu CHSH en utilisant une stratégie générale non-signalante, simplement en définissant $P(ab|xy) := \frac{1}{2}$ si $a \oplus b = x \wedge y$, et $P(ab|xy) := 0$ sinon [PR94].

Les corrélations non-signalantes générales ne représentent pas la réalité physique, car elles
impliquent des comportements non locaux plus forts que ceux qui se produisent dans le
cadre de la mécanique quantique. Cependant, elles présentent un grand intérêt théorique.
Notamment, la description de l'ensemble des corrélations non-signalantes est beaucoup
plus simple que celle des corrélations quantiques, car elles sont caractérisées par de simples
contraintes linéaires; voir [BCP<sup>+</sup>14] pour une revue générale sur la non-localité.

L'algorithme d'approximation pour le problème du codage de canal dans [BF18] s'appuie
en fait sur des codes avec assistance non-signalante. Comme la recherche du meilleur code
avec assistance non-signalante pour un canal est un programme linéaire, il peut être résolu
exactement en temps polynomial. Ils ont mis au point une stratégie pour transformer ce
code avec assistance non-signalante en un code classique, en perdant au maximum un
facteur $1 - e^{-1}$ dans la probabilité de succès. Un énoncé plus précis de cette stratégie
implique en fait que les zones de capacité avec ou sans assistance non-signalante sont les
mêmes, retrouvant un résultat de [Mat12]. Il convient également de noter que l'assistance
non-signalante ne modifie pas la zone de capacité de la tâche inverse de simulation des
canaux [CRBT22]. Ce lien inattendu entre les algorithmes d'approximation pour le problème
du codage de canal et les corrélations non-signalantes est la motivation principale du reste
de la thèse. En particulier, nous développerons ces analyses dans les principaux scénarios
de communication en réseau.

La théorie de l'information des réseaux, qui vise à comprendre la communication sur des
canaux à émetteurs multiples et à récepteurs multiples, a été étudiée pour la première fois par Shannon dans le cas particulier des canaux deux-à-deux [Sha61] (connus aujourd'hui sous le nom de canaux d'interférence). Plus tard, Cover [Cov72] a introduit les canaux de diffusion, avec plusieurs récepteurs mais un seul émetteur. Ahlswede [Ahl73] et indépendamment Liao [Lia73] ont étudié le scénario inverse des canaux à accès multiple, avec plusieurs émetteurs mais un seul récepteur. Ces canaux plus complexes permettent une meilleure modélisation des communications interconnectées réelles.

Contrairement à la situation point-à-point, la non-localité peut augmenter la capacité des canaux en réseau. Quek et Shor ont montré dans [QS17] l'existence de canaux d'interférence à deux émetteurs et deux récepteurs avec des écarts entre leurs zones de capacité classique, avec assistance d'intrication quantique et avec assistance non-signalante. À la suite de ce résultat, Leditzky et al. [LALS20, SLSS22] ont montré que l'intrication quantique partagée entre les deux émetteurs d'un canal à accès multiple peut strictement agrandir sa zone de capacité.

Nous aborderons le problème du codage pour les canaux à accès multiple et les canaux de diffusion. Nous étudierons l'impact des corrélations non-signalantes sur leurs capacités, ainsi que leurs liens avec les algorithmes d'approximation des problèmes de codage associés.

**Résumé des chapitres** Dans le Chapitre 3 (basé sur [BFF21]), nous considérons la généralisation suivante du problème de couverture multiple maximale de paramètre $\ell$ dépendant d'une fonction croissante concave $\varphi : $ étant donné des sous-ensembles $T_1, \dots, T_m$ d'un univers $[n]$, des poids strictement positifs $w_a$ sur l'univers $[n]$ et d'un entier $k$, l'objectif est de trouver un sous-ensemble $S \subseteq [m]$ de taille $k$ qui maximise $C\varphi(S) := \sum_{a \in [n]} w_a \varphi(|S|_a)$, où $|S|_a := |\{i \in S : a \in T_i\}|$; le problème de couverture multiple maximale de paramètre $\ell$ est retrouvé en prenant $\varphi(x) := \min(x, \ell)$. Pour tout $\varphi$ de ce type, nous fournissons un algorithme efficace qui permet d'obtenir un rapport d'approximation égal au rapport de concavité de Poisson de $\varphi$, défini par $\alpha_\varphi := \min_{x \in \mathbb{N}^*} \frac{\mathbb{E}[\varphi(\text{Poi}(x))]}{\varphi(\mathbb{E}[\text{Poi}(x)])}$. En complément de cette garantie d'approximation, nous établissons un résultat de NP-difficulté lorsque $\varphi$ croît de manière sous-linéaire. 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 obtenons 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. Notre résultat dépasse ce cadre particulier et nous l'illustrons par des applications aux problèmes d'allocation de ressources distribuées, aux problèmes de maximisation de la prospérité et au vote basé sur l'approbation pour des règles générales.

Dans le Chapitre 4 (basé sur [FF22, FF23]), nous abordons le problème du codage pour les canaux à accès multiple. Nous montrons tout d'abord qu'il ne peut pas être approximé en temps polynomial avec un ratio constant, sous une hypothèse de complexité sur des formules $k$-SAT aléatoires. Ensuite, nous étudions l'influence des corrélations non signalantes entre les parties. Nous développons un programme linéaire calculant la probabilité de succès optimale pour le codage sur $n$ copies d'un canal d'accès multiple $W$ dont la taille croît polynomialement en $n$. La résolution de ce programme linéaire nous permet d'obtenir des bornes inférieures pour les canaux à accès multiple. En appliquant cette méthode au canal additionneur binaire, nous montrons qu'en utilisant une assistance non-signalante, la
somme des taux $\frac{\log_2(72)}{4} \approx 1.5425$ peut être atteinte même avec une erreur nulle, ce qui dépasse la capacité maximale de la somme des taux de 1.5 dans le cas sans assistance. Pour les canaux bruités, où la région de capacité avec assistance non-signalante et sans erreur est triviale, nous pouvons utiliser des codes concaténés pour obtenir des points réalisables dans la zone de capacité. Appliqués à une version bruitée du canal additionneur binaire, nous montrons que l'assistance non-signalante améliore encore la capacité. En complément de ces résultats de faisabilité, nous donnons une borne supérieure à la zone de capacité avec assistance non-signalante qui a la même expression que la région sans assistance, sauf que les entrées du canal ne sont pas obligées d'être indépendantes. Enfin, nous montrons que la zone de capacité avec assistance non-signalante partagée uniquement entre chaque émetteur et le récepteur indépendamment est la même que sans assistance.

Dans le Chapitre 5, nous abordons le problème du codage pour les canaux de diffusion. Pour la classe des canaux de diffusion déterministes, nous décrivons un algorithme d'approximation de ratio $(1 - e^{-1})^2$ fonctionnant en temps polynomial, et nous montrons que la zone de capacité pour cette classe est la même avec ou sans assistance non-signalante. Enfin, nous montrons que dans le modèle d'accès par valeur, nous ne pouvons pas obtenir un meilleur ratio d'approximation que $\Omega(\frac{1}{\sqrt{m}})$ en temps polynomial pour le problème général du codage des canaux de diffusion, avec $m$ la taille de l'une des sorties du canal.
<figure><img src="image_4.png" /></figure>
# Background

In this chapter, we recall briefly basic definitions and properties, as well as more unusual results, used throughout the thesis. Rather than an introduction to each of those topics, one should see this chapter as a toolbox and use it when needed in the other chapters.

## 2.1 Probability Theory

### 2.1.1 Usual Distributions and Properties

**Definition 2.1** (Usual Distributions). We will consider the following probability distributions:

1. The Bernoulli distribution $Ber(p)$ is defined on $\{0, 1\}$ with the mass function:

$$ (1 - p, p). $$

2. The binomial distribution $Bin(n, p)$ is defined on $\{0, \dots, n\}$ with the mass function:

$$ \left( \binom{n}{k} p^k (1-p)^{n-k} \right)_{k \in \{0, \dots, n\}} . $$

3. The Poisson distribution $Poi(\lambda)$ is defined on $\mathbb{N}$ with the mass function:

$$ \left( \frac{\lambda^k e^{-\lambda}}{k!} \right)_{k \in \mathbb{N}} . $$

**Proposition 2.1** (Jensen's Inequality [Jen06]). For $X$ random variable and $\varphi$ concave, we have:

$$ \mathbb{E}[\varphi(X)] \leq \varphi(\mathbb{E}[X]). $$

**Proposition 2.2.** For $\varphi$ concave, and $p \in [0, 1]^m$, we have:

$$ \mathbb{E} \left[ \varphi \left( \sum_{i=1}^{m} \mathrm{Ber}(p_i) \right) \right] \geq \mathbb{E} \left[ \varphi \left( \mathrm{Poi} \left( \sum_{i=1}^{m} p_i \right) \right) \right]. $$
*Proof.* The notion of convex order discussed in [SS07] allows us to prove this result. We say that $X \le_{cx} Y \iff \mathbb{E}[f(X)] \le \mathbb{E}[f(Y)]$ for any convex $f$. Thanks to Lemma 2.3 of [BFGG20], we have that for $p \in [0, 1]$:

$$ \mathrm{Ber}(p) \le_{cx} \mathrm{Poi}(p). $$

Since this order is preserved through convolution (Theorem 3.A.12 of [SS07]), and the fact that $\sum_{i=1}^m \mathrm{Poi}(p_i) \sim \mathrm{Poi}(\sum_{i=1}^m p_i)$, we have:

$$ \sum_{i=1}^{m} \mathrm{Ber}(p_i) \le_{cx} \mathrm{Poi} \left( \sum_{i=1}^{m} p_i \right). $$

Applying this result to $-\varphi$, which is convex, concludes the proof. $\square$

### 2.1.2 Negatively Associated Random Variables

We present a weaker notion of independence for random variables which is called negative association as introduced in [JDP83], for which the Chernoff-Hoeffding bounds still hold.

**Definition 2.2.** Random variables $X_1, \dots, X_n$ are said to be negatively associated if for every pair of disjoint subsets $I, J$ of $[n]$ and (coordinate-wise) increasing functions $f, g$, we have:

$$ \mathbb{E}[f(\{X_i : i \in I\}) \cdot g(\{X_i : i \in J\})] \le \mathbb{E}[f(\{X_i : i \in I\})] \cdot \mathbb{E}[g(\{X_i : i \in J\})]. $$

**Proposition 2.3 (Property P₁ of [JDP83]).** A pair of random variable X, Y is negatively associated if and only if:

$$ \forall x \in \mathcal{X}, \forall y \in \mathcal{Y}, P_{XY}(x, y) \le P_X(x)P_Y(y). $$

**Proposition 2.4 (Property P₄ of [JDP83]).** A subset of two or more negatively associated random variables is negatively associated.

**Proposition 2.5 (Property P₅ of [JDP83]).** A set of independent random variables is negatively associated.

**Proposition 2.6 (Property P₆ of [JDP83]).** Increasing functions defined on disjoint subsets of a set of negatively associated random variables are negatively associated.

**Proposition 2.7 (Property P₇ of [JDP83]).** The union of independent sets of negatively associated random variables is negatively associated.

**Definition 2.3 (Permutation Distribution).** Let $x = (x_1, \dots, x_k) \in \mathbb{R}^k$. A permutation distribution is the joint distribution of the vector $X = (X_1, \dots, X_k)$ which takes as values all $k!$ permutations of $x$ with equal probabilities, each being $\frac{1}{k!}$.

**Proposition 2.8 (Theorem 2.11 of [JDP83]).** A permutation distribution is negatively associated.

**Proposition 2.9 (Chernoff-Hoeffding bound - version 1).** Let $X_1, \dots, X_n$ be negatively associated random variables such that $0 \le X_i \le B$ and $\mathbb{E}[X_i] = \mu$. Then for $\eta \in (0, 1)$:

$$ \mathbb{P} \left( \left| \frac{1}{n} \sum_{i=1}^{n} X_i - \mu \right| > \eta \right) \le 2e^{-2(\frac{\eta}{B})^2 n}. $$
**Proof.** This usual version of the Chernoff-Hoeffding bound for independent variables (Theorem 2 of [Hoe63]) can be extended to negatively associated random variables directly as pointed out by [DR98]. □

**Proposition 2.10 (Chernoff-Hoeffding bound - version 2).** Let $X_1, \dots, X_n$ be negatively associated Bernoulli random variables of parameter $p$. Then for $0 < \varepsilon \le \frac{1}{2}$:

$$ \mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n} X_i > (1 + \varepsilon)p\right) \le e^{-\frac{pn\varepsilon^2}{4}}. $$

**Proof.** Usual proofs of the Chernoff-Hoeffding bound work in the same way with negatively associated variables as pointed out by [DR98]. So, one obtain as in the original proof (Theorem 1 of [Hoe63]) that:

$$ \mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n} X_i > (1 + \varepsilon)p\right) \le e^{-D((1+\varepsilon)p||p)n}, $$

with $D(x||y) := x \ln(\frac{x}{y}) + (1-x) \ln(\frac{1-x}{1-y})$ the Kullback-Leibler divergence between Bernoulli distributed random variables with parameters $x$ and $y$. As $D((1+\varepsilon)p||p) \ge \frac{\varepsilon^2 p}{4}$ for $0 < \varepsilon < \frac{1}{2}$, we recover the expected bound. □

### 2.1.3 Non-Signaling Probability Distributions

**Definition 2.4.** We say that a conditional probability distribution $P(a^n|x^n)$ defined on $\times_{i=1}^n A_i \times \times_{i=1}^n \mathcal{X}_i$ is non-signaling if for all $a^n, x^n, \hat{x}^n$, we have

$$ \forall i \in [n], \sum_{\hat{a}_i} P(a_1 \dots \hat{a}_i \dots a_n | x_1 \dots x_i \dots x_n) = \sum_{\hat{a}_i} P(a_1 \dots \hat{a}_i \dots a_n | x_1 \dots \hat{x}_i \dots x_n). $$

**Definition 2.5.** Let $P(a^n|x^n)$ a conditional probability distribution defined on $\times_{i=1}^n A_i \times \times_{i=1}^n \mathcal{X}_i$ and $P'(a'^n|x'^n)$ defined on $\times_{i=1}^n A'_i \times \times_{i=1}^n \mathcal{X}'_i$. We define $P \otimes P'$ the tensor product conditional probability distribution defined on $\times_{i=1}^n (A_i \times A'_i) \times \times_{i=1}^n (\mathcal{X}_i \times \mathcal{X}'_i)$ by $(P \otimes P')(a_1 a'_1 \dots a_n a'_n | x_1 x'_1 \dots x_n x'_n) := P(a^n|x^n) \cdot P'(a'^n|x'^n)$.

**Proposition 2.11.** If both $P$ and $P'$ are non-signaling, then $P \otimes P'$ is non-signaling.

**Proof.** Let $a^n \in \times_{j=1}^n A_j$, $a'^n \in \times_{j=1}^n A'_j$, $x^n \in \times_{j=1}^n \mathcal{X}_j$, $x'^n \in \times_{j=1}^n \mathcal{X}'_j$ and $\hat{x}_i \in \mathcal{X}_i$,
$\hat{x}'_i \in \mathcal{X}'_i$. Using the fact that $P, P'$ are non-signaling, we have:

$$ 
\begin{aligned}
& \sum_{\hat{a}_i \hat{a}'_i} P(a_1 a'_1 \dots \hat{a}_i \hat{a}'_i \dots a_n a'_n | x_1 x'_1 \dots x_i x'_i \dots x_n x'_n) \\
&= \sum_{\hat{a}_i \hat{a}'_i} P(a_1 \dots \hat{a}_i \dots a_n | x_1 \dots x_i \dots x_n) \cdot P'(a'_1 \dots \hat{a}'_i \dots a'_n | x'_1 \dots x'_i \dots x'_n) \\
&= \left( \sum_{\hat{a}_i} P(a_1 \dots \hat{a}_i \dots a_n | x_1 \dots x_i \dots x_n) \right) \cdot \left( \sum_{\hat{a}'_i} P'(a'_1 \dots \hat{a}'_i \dots a'_n | x'_1 \dots x'_i \dots x'_n) \right) \\
&= \left( \sum_{\hat{a}_i} P(a_1 \dots \hat{a}_i \dots a_n | x_1 \dots \hat{x}_i \dots x_n) \right) \cdot \left( \sum_{\hat{a}'_i} P'(a'_1 \dots \hat{a}'_i \dots a'_n | x'_1 \dots \hat{x}'_i \dots x'_n) \right) \\
&= \sum_{\hat{a}_i \hat{a}'_i} (P \otimes P') (a_1 a'_1 \dots \hat{a}_i \hat{a}'_i \dots a_n a'_n | x_1 x'_1 \dots \hat{x}_i \hat{x}'_i \dots x_n x'_n),
\end{aligned} 
\quad (2.1) $$

so $P \otimes P'$ is non-signaling. $\square$

## 2.2 Information Theory

### 2.2.1 Information Quantities

Here, $X, Y, Z$ will denote random variables over finite sets $\mathcal{X}, \mathcal{Y}, \mathcal{Z}$ and we will denote their distributions by $P_X(x) = \mathbb{P}(X = x)$, $P_{X,Y}(x, y) = \mathbb{P}(X = x, Y = y)$, $P_{X|Y}(x|y) = \mathbb{P}(X = x|Y = y), \dots$

**Definition 2.6** ((Shannon) Entropy $H(X)$). The (Shannon) entropy $H(X)$ of $X$ is defined by:

$$ H(X) := \mathbb{E}_X[-\log(P_X(X))] = - \sum_{x \in \mathcal{X}} P_X(x) \log(P_X(x)). $$

The entropy of two random variables $X, Y$ is defined as $H(X, Y) := H((X, Y))$.

**Definition 2.7** (Conditional Entropy $H(X|Y)$). The conditional entropy $H(X|Y)$ of $X$ given $Y$ is defined by:

$$ 
\begin{aligned}
H(X|Y) &:= \sum_{y \in \mathcal{Y}} P_Y(y) H(X|Y = y) \\
&= \sum_{y \in \mathcal{Y}} P_Y(y) \left( - \sum_{x \in \mathcal{X}} P_{X|Y}(x|y) \log(P_{X|Y}(x|y)) \right) \quad (2.2) \\
&= - \sum_{x \in \mathcal{X}, y \in \mathcal{Y}} P_{X,Y}(x, y) \log(P_{X|Y}(x|y)).
\end{aligned}
 $$

**Definition 2.8** (Mutual Information $I(X : Y)$). The mutual information $I(X : Y)$ of $X$ and $Y$ is defined by:

$$ I(X : Y) := \sum_{x \in \mathcal{X}, y \in \mathcal{Y}} P_{X,Y}(x, y) \log \left( \frac{P_{X,Y}(x, y)}{P_X(x) P_Y(y)} \right). $$
**Proposition 2.12.** Equivalently, we have:

$$I(X:Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) = H(X) + H(Y) - H(X,Y).$$

**Definition 2.9 (Conditional Mutual Information I(X : Y | Z)).** The mutual information I(X : Y | Z) of X and Y given Z is defined by:

$$ 
\begin{aligned}
I(X:Y|Z) &:= \sum_{z \in \mathcal{Z}} P_Z(z) I(X:Y|Z=z) \\
&= \sum_{x \in \mathcal{X}, y \in \mathcal{Y}, z \in \mathcal{Z}} P_{X,Y,Z}(x,y,z) \log \left( \frac{P_{X,Y|Z}(x,y|z)}{P_{X|Z}(x|z)P_{Y|Z}(y|z)} \right).
\end{aligned} 
\quad (2.3) $$

**Definition 2.10 (Markov chain X → Y → Z).** We say that X → Y → Z forms a Markov chain if Z is conditionally independent of X given Y, that is to say:

$$\forall x \in \mathcal{X}, \forall y \in \mathcal{Y}, \forall z \in \mathcal{Z}, P_{Z|X,Y}(z|x,y) = P_{Z|Y}(z|y).$$

### 2.2.2 Typical Sets

We consider typical sets as defined in Chapter 2.5 of [GK11]:

**Definition 2.11 (Typical set and conditional typical set).** We have the following definitions:

1. $\mathcal{T}_{\varepsilon}^n(X) := \{x^n: |\pi(x|x^n) - P_X(x)| \le \varepsilon P_X(x) \text{ for all } x \in \mathcal{X}\}$, with the empirical distribution $\pi$ defined by $\pi(x|x^n) := \frac{|\{i: x_i = x\}|}{n}$. This definition generalizes for any t-tuple of variables.

2. $\forall y^n \in \mathcal{T}_{\varepsilon}^n(Y), \mathcal{T}_{\varepsilon}^n(X|y^n) := \{x^n: (x^n, y^n) \in \mathcal{T}_{\varepsilon}^n(X, Y)\}$.

A crucial property of such typical sets is the typical average lemma:

**Lemma 2.13 (Typical Average Lemma [GK11]).** Let $x^n \in \mathcal{T}_{\varepsilon}^n(X)$. Then for any nonnegative function $g$ on $\mathcal{X}$:

$$(1 - \varepsilon)\mathbb{E}[g(X)] \le \frac{1}{n} \sum_{i=1}^{n} g(x_i) \le (1 + \varepsilon)\mathbb{E}[g(X)].$$

In particular, with this tool, we can derive the following properties:

**Proposition 2.14 (Properties of typical sets [GK11]).** We have, among others, the following statements about typical sets:

1. $\forall x^n \in \mathcal{T}_{\varepsilon}^n(X), 2^{-n(1+\varepsilon)H(X)} \le P_{X^n}(x^n) \le 2^{-n(1-\varepsilon)H(X)}$.

2. $\lim_{n \to +\infty} \mathbb{P}(X^n \in \mathcal{T}_{\varepsilon}^n(X)) = 1$.

3. $|\mathcal{T}_{\varepsilon}^n(X)| \le 2^{n(1+\varepsilon)H(X)}$.

4. For $n$ sufficiently large, $|\mathcal{T}_{\varepsilon}^n(X)| \ge (1 - \varepsilon)2^{n(1-\varepsilon)H(X)}$.

5. If $(x^n, y^n) \in \mathcal{T}_{\varepsilon}^n(X, Y)$ then $x^n \in \mathcal{T}_{\varepsilon}^n(X)$ and $y^n \in \mathcal{T}_{\varepsilon}^n(Y)$.
6. $\forall y^n \in \mathcal{T}_{\varepsilon}^n(Y), \mathcal{T}_{\varepsilon}^n(X|y^n) \subseteq \mathcal{T}_{\varepsilon}^n(X).$

7. $\forall (x^n, y^n) \in \mathcal{T}_{\varepsilon}^n(X, Y), 2^{-n(1+\varepsilon)H(X|Y)} \le P_{X^nY^n}(x^n|y^n) \le 2^{-n(1-\varepsilon)H(X|Y)}.$

8. $\forall y^n \in \mathcal{T}_{\varepsilon}^n(Y), |\mathcal{T}_{\varepsilon}^n(X|y^n)| \le 2^{n(1+\varepsilon)H(X|Y)}.$

9. For $\varepsilon' < \varepsilon$ and $n$ sufficiently large, we have that $\forall y^n \in \mathcal{T}_{\varepsilon'}^n(Y), |\mathcal{T}_{\varepsilon'}^n(X|y^n)| \ge (1-\varepsilon)2^{n(1-\varepsilon)H(X|Y)}.$

*Proof.* We reproduce the proof of the last statement here to emphasize on the fact that there is an $n_0$ such that for all $n \ge n_0$ and for all $y^n \in \mathcal{T}_{\varepsilon'}^n(Y)$, the property holds.

For any $\varepsilon > \varepsilon' > 0$, let us show that there exists $n$ such that we have:

$$ \forall y^n \in \mathcal{T}_{\varepsilon'}^n(Y), \mathbb{P}((X^n, y^n) \in \mathcal{T}_{\varepsilon}^n(X, Y)) \ge 1 - \varepsilon, $$

where $X^n$ are drawn from the distribution $P_{X^n|Y^n=y^n}$. This will imply the statement. Indeed, we have that:

$$ \begin{aligned} \mathbb{P}((X^n, y^n) \in \mathcal{T}_{\varepsilon}^n(X, Y)) &= \sum_{x^n \in \mathcal{T}_{\varepsilon}^n(X|y^n)} P_{X^n|Y^n}(x^n|y^n) \\ &\le |\mathcal{T}_{\varepsilon}^n(X|y^n)|2^{-n(1-\varepsilon)H(X|Y)}, \end{aligned} \quad (2.4) $$

since $P_{X^n|Y^n}(x^n|y^n) \le 2^{-n(1-\varepsilon)H(X|Y)}$ as $(x^n, y^n) \in \mathcal{T}_{\varepsilon}^n(X, Y)$. Thus, we have that $|\mathcal{T}_{\varepsilon}^n(X|y^n)| \ge (1-\varepsilon)2^{n(1-\varepsilon)H(X|Y)}$. In order to prove our result, we take the proof in Appendix 2A of [GK11]. We take $y^n \in \mathcal{T}_{\varepsilon'}^n(\mathcal{Y})$ and $X^n \sim P_{X^n|Y^n}(x^n|y^n) = \prod_{i=1}^n P_{X_i|Y_i}(x_i|y_i)$. Applied to our choice of variables, we have that $\mathbb{P}((X^n, y^n) \notin \mathcal{T}_{\varepsilon}^n(X, Y))$ is equal to:

$$ \begin{aligned} & \mathbb{P}(\exists(x, y) : |\pi(x, y|X^n, y^n) - P_{XY}(x, y)| > \varepsilon P_{XY}(x, y)) \\ & \le \sum_{x,y} \mathbb{P}(|\pi(x, y|X^n, y^n) - P_{XY}(x, y)| > \varepsilon P_{XY}(x, y)) \\ & = \sum_{x,y} \mathbb{P}\left(\left|\frac{\pi(x, y|X^n, y^n)}{P_{XY}(x, y)} - 1\right| > \varepsilon\right) \\ & = \sum_{x,y} \mathbb{P}\left(\left|\frac{\pi(x, y|X^n, y^n)}{P_{X|Y}(x|y)\pi(y|y^n)} - \frac{\pi(y|y^n)}{P_{Y}(y)} - 1\right| > \varepsilon\right) \quad (2.5) \\ & \le \sum_{x,y} \mathbb{P}\left(\frac{\pi(x, y|X^n, y^n)}{\pi(y|y^n)} > \frac{1+\varepsilon}{1+\varepsilon'} P_{X|Y}(x|y)\right) \\ & \quad + \sum_{x,y} \mathbb{P}\left(\frac{\pi(x, y|X^n, y^n)}{\pi(y|y^n)} < \frac{1-\varepsilon}{1-\varepsilon'} P_{X|Y}(x|y)\right), \end{aligned} $$

since $y^n \in \mathcal{T}_{\varepsilon'}^n(\mathcal{Y})$ and thus $1 - \varepsilon' \le \frac{\pi(y|y^n)}{P_{Y}(y)} \le 1 + \varepsilon'$. However, since $\varepsilon' < \varepsilon$, we have $\frac{1+\varepsilon}{1+\varepsilon'} > 1$ and $\frac{1-\varepsilon}{1-\varepsilon'} < 1$. We will show that for all $x, y$ with $P_{Y}(y) > 0$, we have $\frac{\pi(x,y|X^n,y^n)}{\pi(y|y^n)} \xrightarrow{n \to +\infty} P_{X|Y}(x|y)$ in probability, with a convergence rate independent of $y^n \in \mathcal{T}_{\varepsilon'}^n(Y)$, which will be enough to conclude the proof.

Let us fix some $x, y$ with $P_{Y}(y) > 0$. Since $y^n \in \mathcal{T}_{\varepsilon'}^n(Y)$, we have in particular that $(1 - \varepsilon')P_{Y}(y) \le \pi(y|y^n) \le (1 + \varepsilon')P_{Y}(y)$. Thus $N := |\{i : y_i = y\}| = n\pi(y|y^n) \ge$
$(1 - \varepsilon')P_Y(y)n$. Then we have:

$$ \frac{\pi(x, y|X^n, y^n)}{\pi(y|y^n)} = \frac{1}{N} \sum_{i \in S} Z_i \text{ with } Z_i := 1_{X_i=x} \text{ and } S := \{i : y_i = y\}. $$

Thus, all $Z_i$ with $i \in S$ are independent and follow the same law:

$$ Z_i := \begin{cases} 1 & \text{with probability } P_{X|Y}(x|y), \\ 0 & \text{otherwise.} \end{cases} $$

Furthermore, we have $\mathbb{E}[Z_i] = P_{X|Y}(x|y)$, and all $Z_i$ have the same variance $\sigma_{x|y}^2 < +\infty$ (depending only on $X, Y, x, y$). Thus we can apply Chebyshev inequality:

$$ \mathbb{P}\left(\left|\frac{1}{N}\sum_{i \in S} Z_i - P_{X|Y}(x|y)\right| \ge \eta\right) \le \frac{\sigma_{x|y}^2}{N\eta^2}. $$

However, since $N \ge (1 - \varepsilon')P_Y(y)n$, we get:

$$ \mathbb{P}\left(\left|\frac{\pi(x, y|X^n, y^n)}{\pi(y|y^n)} - P_{X|Y}(x|y)\right| \ge \eta\right) \le \frac{\sigma_{x|y}^2}{\eta^2(1 - \varepsilon')P_Y(y)n} \xrightarrow{n \to +\infty} 0. $$

Thus, we have $\frac{\pi(x,y|X^n,y^n)}{\pi(y|y^n)} \xrightarrow{n \to +\infty} P_{X|Y}(x|y)$ in probability with a convergence rate independent of $y^n \in \mathcal{T}_{\varepsilon'}^n(Y)$. $\square$

### 2.2.3 Channels

Formally, a channel $W$ is a conditional probability distribution depending on $n$ inputs belonging to $\mathcal{X}^n$ and $m$ outputs belonging to $\mathcal{Y}^m$, so $W := (W(y^m|x^n))_{x^n \in \mathcal{X}^n, y^m \in \mathcal{Y}^m}$ with:

$$ \forall x^n, y^m, W(y^m|x^n) \ge 0 \text{ and } \forall x^n, \sum_{y^m \in \mathcal{Y}^m} W(y^m|x^n) = 1. $$

We will denote such a channel by $W: \mathcal{X}^n \to \mathcal{Y}^m$. The tensor product of two channels $W: \mathcal{X}^n \to \mathcal{Y}^m$ and $W': \mathcal{X}'^n \to \mathcal{Y}'^m$ is denoted by $W \otimes W': (\mathcal{X}^n \times \mathcal{X}'^n) \to (\mathcal{Y}^n \times \mathcal{Y}'^m)$ and defined by:

$$ (W \otimes W')(y^m y'^m | x^n x'^n) := W(y^m | x^n) \cdot W'^m(x'^n). $$

We denote by $W^{\otimes n}$ the nth tensor product of $W$, i.e. $W^{\otimes n} = W \otimes \dots \otimes W$ with $n$ occurrences of $W$.

When $n = m = 1$, we will speak of regular or point-to-point channels. When $n > 1, m = 1$, we will speak of multiple-access channels. When $n = 1, m > 1$, we will speak of broadcast channels. If both $n, m$ are greater than 1, we will speak of interference channels. More specifically, in this thesis, we will focus on the cases of $n = 2, m = 1$ and $n = 1, m = 2$, which are at the core of the specificity of network channels.
### 2.2.4 Capacity Regions

**Definition 2.12** (Capacity Region $C[S](W)$ for a success probability $S(W, k_1, k_2)$). A rate pair $(R_1, R_2)$ is S-achievable (for the channel $W$) if:

$$ \lim_{n \to +\infty} S(W^{\otimes n}, [2^{R_1 n}], [2^{R_2 n}]) = 1. $$

We define the S-capacity region $C[S](W)$ as the closure of the set of all achievable rate pairs (for the channel $W$).

**Definition 2.13** (Zero-error Capacity Region $C_0[S](W)$ for $S(W, k_1, k_2)$). A rate pair $(R_1, R_2)$ is S-achievable with zero-error (for the channel $W$) if:

$$ \exists n_0 \in \mathbb{N}^*, \forall n \ge n_0, S(W^{\otimes n}, [2^{R_1 n}], [2^{R_2 n}]) = 1. $$

We define the zero-error S-capacity region $C[S](W)$ as the closure of the set of all achievable rate pairs with zero-error (for the channel $W$).

**Proposition 2.15** (Time-sharing). If the success probability $S$ satisfies:

$\forall W, W', \forall k_1, k_2, k'_1, k'_2, S(W \otimes W', k_1 k'_1, k_2 k'_2) \ge S(W, k_1, k_2) \cdot S(W', k'_1, k'_2)$, \\
then for all channels $W, C[S](W)$ and $C_0[S](W)$ are convex.

*Proof.* Let $(R_1, R_2)$ and $(R'_1, R'_2)$, two pairs of S-achievable rational rates for $W$, i.e.:

$$ S(W^{\otimes n}, [2^{R_1 n}], [2^{R_2 n}]) \xrightarrow{n \to +\infty} 1 \text{ and } S(W^{\otimes n}, [2^{R'_1 n}], [2^{R'_2 n}]) \xrightarrow{n \to +\infty} 1. $$

Let $\lambda \in (0, 1)$ rational and define $R_{\lambda,i} := \lambda \cdot R_i + (1-\lambda) \cdot R'_i$, let us show that $(R_{\lambda,1}, R_{\lambda,2})$ is achievable with non-signaling assistance. Let us call respectively $k_i := 2^{R_i}, k'_i := 2^{R'_i}, k_{\lambda,i} := 2^{R_{\lambda,i}} = k_i^{\lambda} \cdot k_i^{(1-\lambda)}$.

We have $R_{\lambda,i}n = \lambda \cdot R_i n + (1-\lambda) \cdot R'_i n = (\lambda n) \cdot R_i + (1-\lambda)n \cdot R'_i$. This is the idea of time-sharing: for $\lambda n$ copies of the channel, we use the strategy with rate $(R_1, R_2)$ and for the $(1-\lambda)n$ other copies of the channel, we use the strategy with rate $(R'_1, R'_2)$. There exists some $n$ such that $\lambda n, (1-\lambda)n, \lambda n R_i, (1-\lambda)n R'_i$ are integers, since everything is rational. This implies that $k_i^{\lambda n}, k_i^{(1-\lambda)n}, k_{\lambda,i}^n$ are integers. Thus, by hypothesis, we have that $S(W^{\otimes n}, k_{\lambda,1}^n, k_{\lambda,2}^n)$ is larger than or equal to:

$$ S(W^{\otimes (\lambda n)}, k_1^{\lambda n}, k_2^{\lambda n}) \cdot S(W^{\otimes ((1-\lambda)n)}, k_1^{(1-\lambda)n}, k_2^{(1-\lambda)n}) \xrightarrow{n \to +\infty} 1 \cdot 1 = 1. $$

Thus, since $S(W^{\otimes n}, k_{\lambda,1}^n, k_{\lambda,2}^n) \le 1$, we get the result $S(W^{\otimes n}, k_{\lambda,1}^n, k_{\lambda,2}^n) \xrightarrow{n \to +\infty} 1$, so $(R_{\lambda,1}, R_{\lambda,2})$ is S-achievable for the channel $W$. Finally, since $C[S](W)$ is defined as the closure of S-achievable rates for the channel $W$, we get that $C[S](W)$ is convex.

For zero-error capacity regions, since by hypothesis there exists ranks $n_0, n'_0$ such that $S(W^{\otimes n}, [2^{R_1 n}], [2^{R_2 n}]) = 1$ for $n \ge n_0$ and $S(W^{\otimes n}, [2^{R'_1 n}], [2^{R'_2 n}]) = 1$ for $n \ge n'_0$, then in particular we get that for $\lambda n \ge n_0$ and $(1-\lambda)n \ge n'_0$ that $S(W^{\otimes n}, k_{\lambda,1}^n, k_{\lambda,2}^n)$ is larger than or equal to:

$$ S(W^{\otimes (\lambda n)}, k_1^{\lambda n}, k_2^{\lambda n}) \cdot S(W^{\otimes ((1-\lambda)n)}, k_1^{(1-\lambda)n}, k_2^{(1-\lambda)n}) = 1. $$
It is in particular true for $n \ge n_0 := \max(\lceil \frac{n_0}{1-\lambda} \rceil, \lceil \frac{n_0}{\lambda} \rceil)$. As $S^{\text{NS}}(W^{\otimes n}, k_{\lambda,1}^n, k_{\lambda,2}^n) \le 1$, we have for all $n \ge n_0$ that $S^{\text{NS}}(W^{\otimes n}, k_{\lambda,1}^n, k_{\lambda,2}^n) = 1$, i.e. $(R_{\lambda,1}, R_{\lambda,2})$ is S-achievable with zero-error for the channel $W$. Finally, since $C_0[S](W)$ is defined as the closure of S-achievable rates with zero-error for the channel $W$, we get that $C_0[S](W)$ is convex. $\square$

## 2.3 Channel Coding for Point-to-Point Channels

We recall here the main results from [BF18] on channel coding for point-to-point channels, i.e. with one input and one output. Let us first recall the definition of the maximum success probability $S(W, k)$ of transmitting $k$ messages using the channel $W$:

$$ 
\begin{aligned}
S(W, k) &:= \underset{e,d}{\text{maximize}} \quad \frac{1}{k} \sum_{i,x,y} W(y|x)e(x|i)d(i|y) \\
&\text{subject to} \quad \sum_{x \in \mathcal{X}} e(x|i) = 1, \forall i \in [k] \\
& \qquad \sum_{j \in [k]} d(j|y) = 1, \forall y \in \mathcal{Y} \\
& \qquad e(x|i), d(j|y) \ge 0
\end{aligned} 
\qquad (2.6) $$

Then, the following characterization of $S(W, k)$ can be derived:

**Proposition 2.16 (Proposition 2.1 of [BF18]).** $S(W, k) = \frac{1}{k} \max_{S \subseteq \mathcal{X}: |S| \le k} f_W(S)$ with $f_W(S) := \sum_{y \in \mathcal{Y}} \max_{x \in S} W(y|x)$.

One can consider non-signaling assistance shared between the sender and the receiver, which leads to the following maximum success probability:

$$ 
\begin{aligned}
S^{\text{NS}}(W, k) &:= \underset{P}{\text{maximize}} \quad \frac{1}{k} \sum_{i,x,y} W(y|x)P(xi|iy) \\
&\text{subject to} \quad \sum_{x} P(xj|iy) = \sum_{x} P(xj|i'y) \\
& \qquad \sum_{j} P(xj|iy) = \sum_{j} P(xj|iy') \qquad (2.7) \\
& \qquad \sum_{x,j} P(xj|iy) = 1 \\
& \qquad P(xj|iy) \ge 0
\end{aligned} 
$$

A symmetrization can also be done to simplify the expression of the linear program defining $S^{\text{NS}}(W, k)$:
**Proposition 2.17** (Appendix A of [BF18]).

$$
\begin{equation}
\begin{aligned}
S^{\text{NS}}(W, k) = & \underset{r,p}{\text{maximize}} \quad \frac{1}{k} \sum_{x,y} W(y|x)r_{x,y} \\
& \text{subject to} \quad \sum_{x} r_{x,y} = 1 \\
& \quad \sum_{x} p_x = k \\
& \quad 0 \le r_{x,y} \le p_x
\end{aligned}
\tag{2.8}
\end{equation}
$$

Finally, the main tool we will use from [BF18] is the following random coding technique,
which describes how to find a classical code with a success probability close to the non-
signaling assisted one:

**Theorem 2.18** (Theorem 3.1 of [BF18]). *Given a solution r, p of the program computing S<sup>NS</sup>(W, k), we have that:*

$$
\mathbb{E}_S \left[ \frac{f_W(S)}{\ell} \right] \ge \frac{k}{\ell} \left( 1 - \left( 1 - \frac{1}{k} \right)^{\ell} \right) \cdot \frac{1}{k} \sum_{x,y} W(y|x) r_{x,y},
$$

for the multiset S obtained by choosing $\ell$ elements of $\mathcal{X}$ independently according to the dis-
tribution $(\frac{p_x}{k})_{x \in \mathcal{X}}$.
Tight Approximation Guarantees
for Concave Coverage Problems

Coverage functions are central objects of study in combinatorial optimization. Problems related to optimizing such functions arise in multiple fields, such as operations research [CFN77], machine learning [FK14], algorithmic game theory [DV15], and information theory [BF18]. The most basic covering problem is the *maximum coverage* one. In this problem, we are given subsets $T_1, \dots, T_m$ of a universe $[n]$, along with a positive integer $k$, and the objective is to find a size-$k$ subset $S \subseteq [m]$ that maximizes the coverage function $C(S) := |\cup_{i \in S} T_i|$. A fundamental result in the field of approximation algorithms establishes that an approximation ratio of $1 - e^{-1}$ can be achieved for this problem in polynomial time [Hoc97] and, in fact, this approximation guarantee is tight, under the assumption that $P \neq \mathrm{NP}$ [Fei98].

Note that in the maximum coverage problem, an element $a \in [n]$ is counted at most once in the objective, even if $a$ appears in several selected sets. However, if we think of elements $a \in [n]$ as goods or resources, there are many settings wherein the utility indeed increases with the number of copies of $a$ that get accumulated. Motivated, in part, by such settings, we consider a generalization of the maximum coverage problem where an element $a$ can contribute by an amount that depends on the number of times it is covered.

Given a function $\varphi: \mathbb{N} \to \mathbb{R}_+$, an integer $k \in \mathbb{N}$, a universe of elements $[n]$, positive weights $w_a$ for each $a \in [n]$, and subsets $T_1, \dots, T_m \subseteq [n]$, the $\varphi$-MAXCOVERAGE problem entails maximizing $C^\varphi(S) := \sum_{a \in [n]} w_a \varphi(|S|_a)$ over subsets $S \subseteq [m]$ of cardinality $k$; here $|S|_a = |\{i \in S : a \in T_i\}|$.

This chapter focuses on functions $\varphi$ that are nondecreasing and concave (i.e., $\varphi(i+2) - \varphi(i+1) \le \varphi(i+1) - \varphi(i)$ for $i \in \mathbb{N}$). We will also assume that the function $\varphi$ is normalized in the sense that $\varphi(0) = 0$ and $\varphi(1) = 1$.<fnref n="1" /> Our approximation guarantees are in terms of the *Poisson concavity ratio* of $\varphi$, which we define as follows:

$$ \alpha_{\varphi} := \inf_{x \in \mathbb{N}^*} \frac{\mathbb{E}[\varphi(\mathrm{Poi}(x))]}{\varphi(\mathbb{E}[\mathrm{Poi}(x)])} = \inf_{x \in \mathbb{N}^*} \frac{\mathbb{E}[\varphi(\mathrm{Poi}(x))]}{\varphi(x)}. \quad (3.1) $$

<footnote n="1">¹One can always replace a generic $\varphi$ to a normalized one without changing the optimal solutions through a simple affine transformation.</footnote>
Here $\text{Poi}(x)$ denotes a Poisson-distributed random variable with parameter $x$. We will write $\alpha_{\varphi}(x) := \frac{\mathbb{E}[\varphi(\text{Poi}(x))]}{\varphi(x)}$, with $\alpha_{\varphi}(0) = 1$, and hence (see Proposition 3.18), $\alpha_{\varphi} = \min_{x \in \mathbb{N}^*} \alpha_{\varphi}(x) = \inf_{x \in \mathbb{R}_+} \alpha_{\varphi}(x)^2$.

Our main result is that the $\varphi$-MAXCOVERAGE problem admits an efficient $\alpha_{\varphi}$-approximation algorithm, when $\varphi$ is normalized nondecreasing concave, and this approximation guarantee is tight when $\varphi$ grows sublinearly. Formally,

**Theorem 3.1.** For any normalized nondecreasing concave function $\varphi$, there exists a $\alpha_{\varphi}$-approximation algorithm for the $\varphi$-MAXCOVERAGE problem running in polynomial time. Furthermore, for $\varphi(n) = o(n)$, it is NP-hard to approximate the $\varphi$-MAXCOVERAGE problem within a factor better than $\alpha_{\varphi} + \varepsilon$, for any constant $\varepsilon > 0$, even restricted to instances with unit weights and regular subsets.

Before detailing the proof of the theorem, we provide a few remarks and connections to related work.

**Applications and related work** We can directly reduce the standard maximum coverage problem to $\varphi$-MAXCOVERAGE by setting $\varphi(j) = \min(j, 1)$. In this case $\alpha_{\varphi} = 1 - e^{-1}$. One can also encapsulate, within our framework, the $\ell$-MULTICOVERAGE problem studied in [BFGG20] by instantiating $\varphi(j) = \min(j, \ell)$. In this setting, we recover the approximation ratio $\alpha_{\varphi} = 1 - \frac{\ell^\ell e^{-\ell}}{\ell!}$, which matches the approximation guarantee obtained in [BFGG20] (see Proposition 3.31). Note that the hardness result in [BFGG20] was based on the unique games conjecture, whereas here we prove that this guarantee is tight under $P \neq \text{NP}$.

The initial motivation for studying $\varphi$-MAXCOVERAGE was to generalize the $\ell$-MULTICOVERAGE problem studied in [BFGG20] as well as its $\ell$-list-decoding interpretation. In the channel coding problem [BF18], we are given a noisy channel $W(y|x)$, defined as a conditional probability distribution, and the goal is to send a message chosen uniformly in $[k]$ through this channel. In order to do so, the sender encodes the input message in $\mathcal{X}$, and the receiver decodes back the output of the channel from $\mathcal{Y}$ to $[k]$. The objective is to find a code that maximize the probability of successfully decoding the message. In the $\ell$-list-decoding problem [Eli57, Woz58], instead of decoding the output into a single message, the decoder outputs a list of size $\ell$ of possible messages, where $\ell$ is some fixed parameter common to all lists. We consider that the decoding is successful if the initial message belongs to that list. The generalization of that problem, which we call the $\varphi$-list-decoding problem, allows decoding lists of any size. However, the decoding will be successful only with probability $\frac{\varphi(\ell)}{\ell}$ when the initial message belongs to that list, where $\ell$ is the size of that list. One can see that with a coverage function $\varphi(j) = \min(j, \ell)$, we recover the $\ell$-list-decoding problem. When the channel is of the form $W(y|x) = \frac{1}{t}$ for $y \in T_x$ with $|T_x| = t$ and $W(y|x) = 0$ elsewhere, the success probability of the $\varphi$-list-decoding problem for a code $S \subseteq \mathcal{X}$ can be written as $\frac{1}{kt} \sum_{y \in \mathcal{Y}} \varphi(|S|_y)$, with $|S|_y = |\{x \in S : y \in T_x\}|$, which is a particular instance of the $\varphi$-MAXCOVERAGE problem; see Section 3.3.1 for further details. Therefore, for that class of channels, a tight approximation ratio $\alpha_{\varphi}$ follows from Theorem 3.1.

<footnote n="2">²We require $\varphi$ to be defined for nonnegative integers and will extend it over $\mathbb{R}_+$ by considering its piecewise linear extension.</footnote>
Another application of $\varphi$-MAXCOVERAGE is in the context of multiwinner elections that entail selecting $k$ (out of $m$) candidates with the objective of maximizing the cumulative utility of $n$ voters; here, the utility of each voter $a \in [n]$ increases as more and more approved (by $a$) candidates get selected. One can reduce multiwinner elections to a coverage problem by considering subset $T_i \subseteq [n]$ as the set of voters that approve of candidate $i \in [m]$ and $\varphi(j)$ as the utility that an agent achieves from $j$ approved selections.<fnref n="3" /> Addressing multiwinner elections in this standard utilitarian model, Dudycz et al. [DMMS20] obtain tight approximation guarantees for some well-studied classes of utilities. Specifically, the result in [DMMS20] applies to the classic proportional approval voting rule, which assigns a utility of $\sum_{i=1}^j \frac{1}{i}$ for $j$ approved selections. This voting rule corresponds to the coverage problem with $\varphi(j) = \sum_{i=1}^j \frac{1}{i}$, which we denote as the PROPORTIONAL APPROVAL VOTING problem (PAV for short). Section 3.3.2 shows that Theorem 3.1 holds for all the settings considered in [DMMS20] and, in fact, applies more generally. In particular, the voting version of $\ell$-MULTICOVERAGE (studied in [SFL16]) can be addressed by Theorem 3.1, but not by the result in [DMMS20]. Such a separation also arises when one truncates the proportional approval voting rule to, say, $\ell$ candidates, i.e., upon setting $\varphi(j) = \sum_{i=1}^{\min(j, \ell)} \frac{1}{i}$. Given that multiwinner elections model multiple real-world settings (e.g., committee selection [SFL16] and parliamentary proceedings [BLS17]), instantiations of $\varphi$-MAXCOVERAGE in such social-choice contexts substantiate the applicability of our algorithmic result.

Coverage functions arise in numerous resource-allocation settings, such as sensor allocation [MW08], job scheduling, and plant location [CFN77]. The goal, broadly, in such setups is to select $k$ subsets of resources (out of $m$ pre-specified ones) such that the welfare generated by the selected resources is maximized–each resource’s contribution to the welfare increases with the number of times it is selected. This problem can be cast as $\varphi$-MAXCOVERAGE by setting $n$ to be the number of resources, $\{T_i\}_{i \in [m]}$ as the given collection of subsets, and $\varphi(j)$ to be the welfare contribution of a resource when it is covered $j$ times.<fnref n="4" /> Here, we mention a specific allocation problem to highlight the relevance of studying $\varphi$ beyond the standard coverage and $\ell$-coverage formulations (see Section 3.3.4 for details): in the VEHICLE-TARGET ASSIGNMENT problem [Mur00, PM18] (VTA for short) the resources are $n$ targets and covering a target $j$ times contributes $\varphi^p(j) = \frac{1-(1-p)^j}{p}$ to the welfare; here, $p \in (0, 1)$ is a given parameter. Interestingly, we find that for this problem, the approximation ratio $\alpha_\varphi$ we obtain can outperform the Price of Anarchy (PoA), which corresponds to the approximation ratio of any method wherein the agents selfishly maximize their utilities (see Section 3.3.4 for further discussion of this point). By contrast, in the resource allocation problem with $\varphi(j) = \min(j, \ell)$, the price of anarchy is equal to $\alpha_\varphi$; see [CPM19] for details. Another allocation problem studied in [PM18] corresponds to $\varphi$-MAXCOVERAGE with $\varphi(j) = j^d$, for a given parameter $d \in (0, 1)$. We refer to this instantiation as the $d$-POWER function.

Theorem 3.1 gives us a tight approximation bound of $\alpha_\varphi$ for all the above-mentioned applications of $\varphi$-MAXCOVERAGE. The values of $\alpha_\varphi$ for these instantiations are listed in Table 3.1.

<footnote n="3">³Indeed, for a subset of candidates $S \subseteq [m]$, the utility of a voter $a \in [n]$ is equal to $\varphi(|S|_a)$, with $|S|_a = |\{i \in S : a \in T_i\}|$.</footnote>

<footnote n="4">⁴Formally, to capture specific welfare-maximization problems in their entirety we have to consider $\varphi$-MAXCOVERAGE with a matroid constraint, and not just bound the number of selected subsets by $k$. Details pertaining to matroid constraints and the reduction appear in Section 3.1.1 and 3.3.3, respectively.</footnote>
<table><caption>Table 3.1 – Tight approximation ratios for particular choices of φ in the φ-MAXCOVERAGE problem.</caption><thead><tr><th>φ-MAXCOVERAGE</th><th>φ(j)</th><th>α<sub>φ</sub></th><th>Derivation</th></tr></thead><tbody><tr><td>MAXCOVERAGE</td><td>min(j, 1)</td><td>1 - e<sup>-1</sup></td><td>Prop. 3.31</td></tr><tr><td>ℓ-MULTICOVERAGE</td><td>min(j, ℓ)</td><td>1 - (e<sup>-ℓ</sup> / ℓ!)</td><td>Prop. 3.31</td></tr><tr><td>PAV</td><td>∑<sub>i=1</sub><sup>j</sup> (1/i)</td><td>α<sub>φ</sub>(1) ≈ 0.7965...</td><td>Prop. 3.28</td></tr><tr><td>PAV capped at 3</td><td>min(j,3) (1/i)</td><td>α<sub>φ</sub>(1) ≈ 0.7910...</td><td>Prop. 3.21</td></tr><tr><td>p-VTA</td><td>(1-p)<sup>j</sup></td><td>(1-e<sup>-p</sup>) / p</td><td>Prop. 3.32</td></tr><tr><td>0.1-VTA</td><td>(1-0.1)<sup>j</sup> / (0.1)</td><td>(1-e<sup>-0.1</sup>) / (0.1)</td><td>Prop. 3.32</td></tr><tr><td>0.1-VTA capped at 5</td><td>min(j,5) / (0.1)</td><td>α<sub>φ</sub>(5) ≈ 0.8470...</td><td>Prop. 3.21</td></tr><tr><td>d-POWER</td><td>j<sup>d</sup></td><td>e<sup>-1</sup> ∑<sub>k=1</sub><sup>+∞</sup> (k/d) / k!</td><td>Prop. 3.33</td></tr></tbody></table>

It is relevant to compare the approximation guarantee, $\alpha_{\varphi}$, obtained here with the approximation ratio based on the notion of curvature of submodular functions. Note that if $\varphi$ is nondecreasing and concave, then $C^{\varphi}$ is submodular. One can show, via a direct calculation, that for such a submodular $C^{\varphi}$ the curvature (as defined in [CC84]) is given by $c = 1 - (\varphi(m) - \varphi(m-1))$ for instances with at most $m$ cover sets; see Proposition 3.19. Therefore, the algorithm of Sviridenko et al. [SVW17] provides an approximation ratio of $1 - ce^{-1}$ for the $\varphi$-MAXCOVERAGE problem. We note that the Poisson concavity ratio $\alpha_{\varphi}$ is always greater than or equal to this curvature-dependent ratio (Proposition 3.22). Specifically, for p-VEHICLE-TARGET ASSIGNMENT, it is strictly better for all $p \notin \{0, 1\}$ and for $\ell$-MULTICOVERAGE, it is strictly better for all $\ell \ge 2$ as remarked in [BFGG20]. Therefore, for the setting at hand, we improve the approximation guarantee obtained in [SVW17].

**Remarks on the Poisson concavity ratio $\alpha_{\varphi}$**. By Jensen's inequality along with the nonnegativity and concavity of $\varphi$, we have that $\alpha_{\varphi} \in [0, 1]$. We show that $\alpha_{\varphi}$ can be computed numerically up to any precision $\varepsilon > 0$, in time that is polynomial in $1/\varepsilon$. In fact, Proposition 3.17 shows that $\alpha_{\varphi}(x) \ge 1 - \varepsilon$ for all $x \ge N_{\varepsilon} := \lceil (6/\varepsilon)^4 \rceil$. Thus, we can iterate over all $x \in \{1, 2, \dots, N_{\varepsilon}\}$ and find $\min_{x \in [N_{\varepsilon}]} \alpha_{\varphi}(x)$ up to $\varepsilon$ precision (under reasonable assumptions on $\varphi$). This gives us a method to overall compute $\alpha_{\varphi}$, up to an absolute error of $2\varepsilon$: if $\alpha_{\varphi} \le 1 - \varepsilon$, then computing $\min_{x \in [N_{\varepsilon}]} \alpha_{\varphi}(x)$ (up to $\varepsilon$ precision) suffices. Otherwise, if $\alpha_{\varphi} \ge 1 - \varepsilon$, then $\alpha_{\varphi}(1) \le 1$ provides the desired bound. Furthermore, we note that Proposition 3.16 shows that even if we consider $\alpha_{\varphi}(x)$ over all $x \in \mathbb{R}_+$, an infimum (i.e., the value of $\alpha_{\varphi}$) is achieved at an integer.

**Further hardness under Gap-ETH** Theorem 3.1 shows that, under the assumption $P \neq \text{NP}$, no polynomial-time algorithm can approximate $\varphi$-MAXCOVERAGE within a better ratio than $\alpha_{\varphi}$ for sublinear $\varphi$. One natural question that arises is whether relaxing the running time constraint helps. More precisely, since there are $\binom{m}{k} = O(m^k)$ choices of $k$ cover sets among the $m$ available, a simple exhaustive search algorithm works in time $O(m^k)$. We can ask if FPT algorithms with respect to $k$, running in time $f(k) \cdot m^{o(k)}$ with $f$ an arbitrary function, can do better. As in [DMMS20], we use the result of [Man20] to show in Theorem 3.14 that such algorithms cannot approximate $\varphi$-MAXCOVERAGE within a better
ratio than $\alpha_{\varphi}$ for sublinear $\varphi$, under the Gap-ETH hypothesis [CCK$^+$17]; see Section 3.2.3 for more details. This means that the brute-force strategy is essentially the best, if one wants to get a better approximation ratio than $\alpha_{\varphi}$.

**Proof techniques and organization** In Section 3.1, we present our approximation algorithm for the $\varphi$-MAXCOVERAGE. The algorithm is an application of pipage rounding, a technique introduced in [AS04], on a linear programming relaxation of $\varphi$-MAXCOVERAGE. We show that the multilinear extension $F^{\varphi}$ of $C^{\varphi}$ is efficiently computable and thus, we can compute an integer solution $x^{\text{int}}$ from the optimal fractional solution $x^*$ satisfying $C^{\varphi}(x^{\text{int}}) \ge F^{\varphi}(x^*)$. Using the notion of convex order between distributions, we show that $F^{\varphi}(x^*) \ge \sum_{a \in [n]} w_a \mathbb{E}[\varphi(\text{Poi}(|x^*|_a))]$, where $|x|_a = \sum_{i \in [m]: a \in T_i} x_i$. Comparing this to the value $\sum_{a \in [n]} w_a \varphi(|x^*|_a)$ taken by the linear program, we get a ratio given by the Poisson concavity ratio $\alpha_{\varphi}$. The concavity of $\varphi$ is crucial at several steps of the proof: it guarantees that the natural relaxation can be written as a linear program, it is used to relate between sums of Bernoulli random variables and a Poisson random variable via the convex order, as well as for the fact that we can restrict the infimum in the definition of $\alpha_{\varphi}$ to integer values of $x$. The generalization to matroid constraints follows in a standard way and is presented in Section 3.1.1.

In Section 3.2, we present the hardness result for $\varphi$-MAXCOVERAGE. For this, we define a generalization of the partitioning gadget of Feige [Fei98], extending also [BFGG20]. Roughly speaking, for an integer $x_{\varphi} \in \mathbb{N}$, it is a collection of $x_{\varphi}$-covers of the set $[n]$ (an $x$-cover is a collection of subsets such that each element $a \in [n]$ is covered $x$ times, or in other words, its $\varphi$-coverage is $\varphi(x)n$) that are incompatible in the sense that if we take an element from each one of these $x_{\varphi}$-covers, then the $\varphi$-coverage is bounded approximately by $\mathbb{E}[\varphi(\text{Poi}(x_{\varphi}))]n$. Then, we construct an instance of $\varphi$-MAXCOVERAGE from an instance of the NP-hard problem Label Cover (as in [DMMS20]) using such a gadget with $x_{\varphi} \in \text{argmin}_{x \in \mathbb{N}} \alpha_{\varphi}(x)$. Having set up the partitioning gadget, the analysis of the reduction can be obtained by carefully generalizing the reductions of [BFGG20] and [DMMS20].

In Section 3.3, we present different domains of application of our result.

## 3.1 Approximation Algorithm for $\varphi$-MAXCOVERAGE

Fix a function $\varphi : \mathbb{N} \to \mathbb{R}_+$ that is normalized, nondecreasing and concave. The $\varphi$-MAXCOVERAGE problem is defined as follows. The input to the problem is given by positive integers $n, m, t$ and $m$ subsets $T_1, \dots, T_m$ of the set $[n]$ (described as characteristic vectors), the weights $w_a \in \mathbb{Q}_+^*$ for $a \in [n]$ (described as a pair of bitstring of length $t$), as well as an integer $k \in \{1, \dots, m\}$. The output is a subset $S \subseteq [m]$ of size $k$ that maximizes $C^{\varphi}(S) = \sum_{a \in [n]} w_a \varphi(|S|_a)$, where $|S|_a = |\{i \in S : a \in T_i\}|$.

Note that the input to this problem can be specified using $n(m + 2t) + O(\log nmt)$ bits. To reduce the number of parameters, we will assume that $t$ is polynomial in $n$ and $m$, so that a polynomial-time algorithm for this problem means an algorithm that runs in time polynomial in $n$ and $m$. The counting function $\varphi$ is fixed and does not depend on the instance of the problem, but for a given instance the problem only depends on the values $\varphi(0), \varphi(1), \dots, \varphi(m)$. We assume that we have black box access to $\varphi$ and to ensure that all the algorithms run in polynomial time, we assume that $\varphi(j)$ can be described with
a number of bits that is polynomial in $j$ and that this description can be computed in polynomial time.

We now describe the approximation algorithm for $\varphi$-MaxCoverage that we analyze. As described above, we follow the standard relax and round strategy, as in [BFGG20]. First, we define a natural convex relaxation.

**Definition 3.1 (Relaxed program).**

$$
\begin{array}{ll}
\text{maximize} & \displaystyle\sum_{a \in [n]} w_a c_a \\
\text{subject to} & c_a \le \varphi(|x|_a), \forall a \in [n], \text{ with } |x|_a := \sum_{i \in [m]: a \in T_i} x_i & (3.2) \\
& 0 \le x_i \le 1, \forall i \in [m] \\
& \sum_{i=1}^{m} x_i = k.
\end{array}
$$

As previously mentioned, $\varphi$ is defined on $\mathbb{R}_+$ by extending it in a piecewise linear fashion on non-integral points. As such, the constraint $c_a \le \varphi(|x|_a)$ is equivalent to $m$ linear constraints. In fact, we can define $\varphi_j$ to be the linear function $\varphi_j(t) = (\varphi(j) - \varphi(j-1))t - (j-1)\varphi(j) + j\varphi(j-1)$ for $j \in [m]$. Since $\varphi$ is concave, we have that for all $t \in [0, m]$, $\varphi(t) = \min_{j \in [m]} \varphi_j(t)$. Thus, the constraint $c_a \le \varphi(|x|_a)$ is equivalent to $c_a \le \varphi_j(|x|_a)$ for all $j \in [m]$ and so the program from Definition 3.1 can be stated as a linear program. Overall there are $n+m$ variables and $(n+1)m+1$ linear constraints, and by assumption all the coefficients can be described using a number of bits that is polynomial in $n$ and $m$. Hence, an optimal solution of this linear program can be found in polynomial time.

Observe that the program from Definition 3.1 is indeed a relaxation of the $\varphi$-MaxCoverage problem. To see this, given a set $S$ of size $k$, consider the characteristic vector $x \in \{0, 1\}^m$ defined by $x_i = 1$ if and only if $i \in S$. Then for all $a \in [n]$, we can set $c_a = \varphi(|x|_a) = \varphi(|S|_a)$, and we get an objective value of $\sum_{a \in [n]} w_a \varphi(|S|_a)$ which is exactly $C^\varphi(S)$. When solving the program from Definition 3.1, we get an optimal $x^* \in [0, 1]^m$ which is in general not integral. Next, we describe a method to round it to an integral vector $x^{\text{int}} \in \{0, 1\}^m$.

**Rounding** For a submodular function $f: \{0, 1\}^m \to \mathbb{R}$, one can use pipage rounding [AS04, Von07, CCPV11] to transform, in polynomial time, any fractional solution $x \in [0, 1]^m$ satisfying $\sum_{i=1}^m x_i = k$ into an integral vector $x^{\text{int}} \in \{0, 1\}^m$ such that $\sum_{i=1}^m x_i^{\text{int}} = k$ and $F(x^{\text{int}}) \ge F(x)$, where $F$ corresponds to the multilinear extension of $f$, provided that $F(x)$ is computable in polynomial time for a given $x$; see e.g., [Von07, Lemma 3.4]. The multilinear extension $F: [0, 1]^m \to \mathbb{R}$ of $f$ is defined by $F(x_1, \dots, x_m) := \mathbb{E}[f(X_1, \dots, X_m)]$, where $X_i$ are independent random variables with $X_i \sim \text{Ber}(x_i)$, i.e., $X_i \in \{0, 1\}$ with $\mathbb{P}(X_i = 1) = x_i$. Note that $F(x) = f(x)$ for an integral vector $x \in \{0, 1\}^m$.

We apply this strategy to $C^\varphi$, which is shown to be submodular in Proposition 3.19, and the solution $x^*$ of the linear programming relaxation from Definition 3.1. Note that overall the algorithm runs in polynomial time, since here $F(x)$ is computable in polynomial time for a given $x$ (see Proposition 3.23). We now analyze the value returned by the
algorithm. Using the property of pipage rounding, with the notation $X = (X_1, \dots, X_m)$ and $\text{Ber}(x) = (\text{Ber}(x_1), \dots, \text{Ber}(x_m))$, we get:

$$C^{\varphi}(x^{\text{int}}) = \mathbb{E}_{X \sim \text{Ber}(x^{\text{int}})} [C^{\varphi}(X)] \geq \mathbb{E}_{X \sim \text{Ber}(x^*)} [C^{\varphi}(X)].$$

Then, we only need to relate $\mathbb{E}_{X \sim \text{Ber}(x^*)} [C^{\varphi}(X)]$ to the optimal value of the linear programming relaxation 3.1, which can only be larger than the optimal value of the $\varphi$-MAXCOVERAGE problem.

**Theorem 3.2.** Let $x, c$ be a feasible solution of the program from Definition 3.1 and let $X \sim \text{Ber}(x)$. Recalling the definition of $\alpha_{\varphi}$ and $\alpha_{\varphi}(j)$ from (3.1), we have

$$\mathbb{E}_{X \sim \text{Ber}(x)} [C^{\varphi}(X)] \geq \left( \min_{j \in [m]} \alpha_{\varphi}(j) \right) \sum_{a \in [n]} w_a c_a.$$

In particular, this implies that the described polynomial-time algorithm achieves an approximation ratio of $\alpha_{\varphi}$:

$$C^{\varphi}(x^{\text{int}}) \geq \alpha_{\varphi} \sum_{a \in [n]} w_a c_a^* \geq \alpha_{\varphi} \max_{S \subseteq [m]: |S| = k} C^{\varphi}(S).$$

*Proof.* By linearity of expectation and the fact that the weights $w_a$ are positive, it is sufficient to show that for all $a \in [n]$:

$$\mathbb{E}[C_a^{\varphi}(X)] \geq \left( \min_{j \in [m]} \alpha_{\varphi}(j) \right) c_a,$$

where $C_a^{\varphi}(S) := \varphi(|S|_a)$. Note that $|X|_a = \sum_{i \in [m]: a \in T_i} X_i$, and thus:

$$\begin{align}
\mathbb{E}[C_a^{\varphi}(X)] &= \mathbb{E}\left[\varphi\left(\sum_{i \in [m]: a \in T_i} X_i\right)\right] = \mathbb{E}\left[\varphi\left(\sum_{i \in [m]: a \in T_i} \text{Ber}(x_i)\right)\right] \nonumber \\
&\geq \mathbb{E}\left[\varphi\left(\text{Poi}\left(\sum_{i \in [m]: a \in T_i} x_i\right)\right)\right] \quad \text{thanks to Proposition 2.2} \tag{3.3} \\
&= \mathbb{E}[\varphi(\text{Poi}(|x|_a))] \geq \min(\alpha_{\varphi}(|x|_a), \alpha_{\varphi}(\lfloor|x|_a\rfloor))\varphi(|x|_a) \nonumber \\
&\qquad \text{thanks to Proposition 3.16} \nonumber \\
&\geq \left(\min_{j \in [m]} \alpha_{\varphi}(j)\right) \varphi(|x|_a) \geq \left(\min_{j \in [m]} \alpha_{\varphi}(j)\right) c_a. \nonumber
\end{align}$$

□

### 3.1.1 Generalization to Matroid Constraints

Instead of taking a cardinality constraint $k$ on the size of the subset $S$, we look now at general matroid constraints on $S$. Specifically, as input, instead of $k$, we take a matroid $\mathcal{M}$ defined on $[m]$ and given by a set of linear constraints describing its base polytope $B(\mathcal{M})$.
The output is a set $S \in \mathcal{M}$ that maximizes $C^{\varphi}(S)$. Note that the cardinality constraint considered above is the special case where $\mathcal{M}$ is the uniform matroid (composed of all subsets of size at most $k$) with its base polytope $B(\mathcal{M}) = \{x \in [0, 1]^m : \sum_{i=1}^m x_i = k\}$.

We note that in order to establish Theorem 3.2, the cardinality constraint $\sum_{i=1}^m x_i = k$ is not used. Thus, since the pipage rounding strategy applies to matroid constraints $\mathcal{M}$ (see [Von07, Lemma 3.4]), the strategy and the analysis of its efficiency generalize immediately when applied to the following linear program:

**Definition 3.2 (Relaxed program for matroid constraints).**

$$
\begin{array}{ll}
\text{maximize} & \displaystyle\sum_{a \in [n]} w_a c_a \\
\text{subject to} & c_a \le \varphi(|x|_a), \forall a \in [n] \\
& 0 \le x_i \le 1, \forall i \in [m] \\
& x \in B(\mathcal{M}) \quad \text{the base polytope of } \mathcal{M}.
\end{array}
\qquad (3.4)
$$

**Theorem 3.3.** Let $x, c$ a feasible solution of the program from Definition 3.2 and $X \sim \text{Ber}(x)$. Then:

$$
\mathbb{E}_{X \sim \text{Ber}(x)} [C^{\varphi}(X)] \geq \left( \min_{j \in [m]} \alpha_{\varphi}(j) \right) \sum_{a \in [n]} w_a c_a .
$$

In particular, this implies that the described polynomial-time algorithm achieves an approximation ratio of $\alpha_{\varphi}$:

$$
C^{\varphi}(x^{\text{int}}) \geq \alpha_{\varphi} \sum_{a \in [n]} w_a c_a^* \geq \alpha_{\varphi} \max_{S \in \mathcal{M}} C^{\varphi}(S).
$$

**3.2 Hardness of Approximation for $\varphi$-MAXCOVERAGE**

In this section, we establish an inapproximability result for the $\varphi$-MAXCOVERAGE problem with unit weights and regular subsets under cardinality constraints. Throughout this section, we use $\Gamma$ to denote the universe of elements and, hence, an instance of the $\varphi$-MAXCOVERAGE problem consists of $\Gamma$, along with a collection of regular subsets $\mathcal{F} = \{F_i \subseteq \Gamma\}_{i=1}^m$ (i.e. $\forall i \in [m], |F_i| = t$ for some $t$) and an integer $k$. Recall that the objective of this problem is to find a size-$k$ subset $S \subseteq [m]$ that maximizes $C^{\varphi}(S) = \sum_{a \in \Gamma} \varphi(|S|_a)$.

We establish the following theorem in this section:

**Theorem 3.4.** It is NP-hard to approximate the $\varphi$-MAXCOVERAGE problem for $\varphi(n) = o(n)$ within a factor greater than $\alpha_{\varphi} + \varepsilon$ for any $\varepsilon > 0$, even restricted to instances with unit weights and regular subsets.

Our reduction is based on a problem called h-ARYLABELCOVER, which is equivalent to the more standard GAPLABELCOVER problem as will be shown in Appendix 3.5.3.
**Definition 3.3 (h-ARYLABELCOVER).** An instance $\mathcal{G} = (V, E, [L], [R], \{\pi_{e,v}\}_{e \in E, v \in e})$ of h-ARYLABELCOVER is characterized by an h-uniform regular hypergraph $(V, E)$ and constraints $\pi_{e,v} : [L] \to [R]$. Here, each h-uniform hyperedge represents a h-ary constraint. Additionally, for any labeling $\sigma : V \to [L]$, we have the following notions of strongly and weakly satisfied constraints:

* An edge $e = (v_1, \dots, v_h) \in E$ is strongly satisfied by $\sigma$ if:

$$ \forall x, y \in [h], \pi_{e,v_x}(\sigma(v_x)) = \pi_{e,v_y}(\sigma(v_y)). $$

* An edge $e = (v_1, \dots, v_h) \in E$ is weakly satisfied by $\sigma$ if:

$$ \exists x \neq y \in [h], \pi_{e,v_x}(\sigma(v_x)) = \pi_{e,v_y}(\sigma(v_y)). $$

**Proposition 3.5 (δ, h-ARYGAPLABELCOVER).** For any fixed integer $h \ge 2$ and fixed $\delta > 0$, there exists an $R_0$ such that for any integer $R \ge R_0$, it is NP-hard for all instances $\mathcal{G} = (V, E, [L], [R], \{\pi_{e,v}\}_{e \in E, v \in e})$ of h-ARYLABELCOVER with right alphabet $[R]$ to distinguish between:

**YES:** There exists a labeling $\sigma$ that strongly satisfies all the edges.

**NO:** No labeling weakly satisfies more than $\delta$ fraction of the edges.

### 3.2.1 Partitioning System

In order to prove Theorem 3.4, we will need to generalize the partitioning system of Feige [Fei98], a constant-size combinatorial object used to prove complexity hardness results. Note that it was already generalized in [BFGG20], over which we base our version. For any set $[n]$ and $Q \subseteq 2^{[n]}$, we overload the definition $C^\varphi(Q) := \sum_{a \in [n]} \varphi(|Q|_a)$ with the notations $|Q|_a := |\{P \in Q : a \in P\}|$ and $C_a^\varphi(Q) := \varphi(|Q|_a)$. Let us take $x_\varphi \in \argmin_{x \in \mathbb{N}^*} \alpha_\varphi(x)$, thus $\alpha_\varphi = \alpha_\varphi(x_\varphi)$.

We say that $Q$ is an $x$-cover of $x \in \mathbb{N}$ if every element of $[n]$ is covered $x$ times, so $C^\varphi(Q) = n\varphi(x)$.

**Definition 3.4.** An $([n], h, R, \varphi, \eta)$-partitioning system consists of $R$ collections of subsets of $[n]$, $\mathcal{P}_1, \dots, \mathcal{P}_R \subseteq 2^{[n]}$, that satisfy $\frac{x_\varphi n}{h} \in \mathbb{N}$, $x_\varphi \ge h$ and:

1. For every $i \in [R]$, $\mathcal{P}_i$ is a collection of $h$ subsets $P_{i,1}, \dots, P_{i,h} \subseteq [n]$ each of size $\frac{x_\varphi n}{h}$ which is an $x_\varphi$-cover.

2. For any $T \subseteq [R]$ and $Q = \{P_{i,j(i)} : i \in T\}$ for some function $j : T \to [h]$, we have $|C^\varphi(Q) - \psi_{|T|,h}^\varphi n| \le \eta n$ where:

$$ \psi_{k,h}^{\varphi} := \mathbb{E} \left[ \varphi \left( \text{Bin} \left( k, \frac{x_{\varphi}}{h} \right) \right) \right]. \qquad (3.5) $$
Remark. In particular, for any $\mathcal{Q} = \{Q_1, \dots, Q_k\}$ with $Q_i$ of size $\frac{x_\varphi n}{h}$, we have that $C\varphi(\mathcal{Q}) \le n\varphi(k\frac{x_\varphi}{h})$. Indeed $C\varphi(\mathcal{Q}) = \sum_{a \in [n]} \varphi(|\mathcal{Q}|_a)$ with $\sum_{a \in [n]} |\mathcal{Q}|_a = \sum_{i \in [k]} |Q_i| = k \cdot \frac{x_\varphi n}{h}$. By concavity of $\varphi$ and Jensen's inequality, this function is maximized when all $|\mathcal{Q}|_a$ are equals, where we get $n\varphi(k\frac{x_\varphi}{h})$.

**Proposition 3.6.** For every choice of $R, h \in \mathbb{N}$ with

$$h \geq x_{\varphi}, \eta \in (0, 1), n \geq \eta^{-2} R \varphi(R)^2 \log(20(h+1))$$

such that $\frac{x_\varphi n}{h} \in \mathbb{N}$, there exists a $([n], h, R, \varphi, \eta)$-partitioning system, which can be found in time $\exp(Rn \log(n)) \cdot \text{poly}(h)$.

The proof can be found in Appendix 3.5.4.

### 3.2.2 The Reduction

*Proof of Theorem 3.4.* Let $\varepsilon > 0$. Without loss of generality, we can assume that $\varepsilon < 1$. We show that it is NP-hard to reach an approximation ratio greater than $\alpha_\varphi + \varepsilon$ for the $\varphi$-MAXCOVERAGE problem, via a reduction from $\delta, h$-ARYGAPLABELCOVER.

* $\eta = \frac{\varphi(x_\varphi)}{4x_\varphi}, \text{ so } 0 < \eta \le \varepsilon < 1,$

* $h \ge x_\varphi$ such that $|\psi_{h,h}^\varphi - \alpha_\varphi\varphi(x_\varphi)| \le \eta$ (see (3.5) for the definition of $\psi^\varphi$); such a choice exists thanks to Proposition 3.24,

* $\theta$ such that for all $x \ge \theta$, $\frac{\varphi(x)}{x} \le \eta$, which exists since $\varphi(x) = o(x),$

* $\xi = \frac{x_\varphi}{\theta},$

* $\delta = \frac{\eta}{2} \frac{\xi^3}{h^2},$

* $R \ge h$ large enough for Proposition 3.5 to hold.

Then, given an instance $\mathcal{G} = (V, E, [L], [R], \Sigma, \{\pi_{e,v}\}_{e \in E, v \in e})$ of $\delta, h$-ARYGAPLABELCOVER, we construct an instance $(\Gamma, \mathcal{F}, k)$ of the $\varphi$-MAXCOVERAGE problem with:

* $n$ a large enough integer to have the existence of $([n], h, R, \varphi, \eta)$-partitioning systems using Proposition 3.6. Note that the size of these partitioning systems is independent of the size of the instance $\mathcal{G}$ and that we can construct such a partitioning system in constant time (with relation to the size of the instance $\mathcal{G}$) thanks to Proposition 3.6.

* $\Gamma = [n] \times E,$

* $k = |V|,$

* Consider a $([n], h, R, \varphi, \eta)$-partitioning system, and call $\mathcal{P} = \{\mathcal{P}_1, \dots, \mathcal{P}_R\}$ the corresponding set of collections. Define sets $T_\beta^{e,v_j} := P_{\pi_{e,v_j}(\beta),j} \times \{e\}$ where $e = (v_1, \dots, v_h) \in E, j \in [h], \beta \in [L]$. Then, take $F_\beta^v := \bigsqcup_{e \in E: v \in e} T_\beta^{e,v}$ as cover sets and $\mathcal{F} := \{F_\beta^v, v \in V, \beta \in [L]\}$. Note that $|F_\beta^v| = \sum_{e \in E: v \in e} |T_\beta^{e,v}| = \sum_{e \in E: v \in e} |P_{\pi_{e,v_j}(\beta),j}| = |\{e \in E: v \in e\}| \cdot \frac{x_\varphi n}{h}$ which does not depend on $v$ as the hypergraph $(V, E)$ is regular. Therefore, those subsets are indeed regular.
We will now prove that if we are in a YES instance, we have that there exists $\mathcal{T}$ of size $k$ such that $C^{\varphi}(\mathcal{T}) \ge \varphi(x_{\varphi})|\Gamma|$ (completeness). Moreover, if we are in a NO instance, then we have that for all $\mathcal{T}$ of size $k = |V|$, $C^{\varphi}(\mathcal{T}) \le (\alpha_{\varphi} + \varepsilon)\varphi(x_{\varphi})|\Gamma|$ (soundness). Establishing these two properties would conclude the proof. In fact, an algorithm for $\varphi$-MAXCOVERAGE achieving a factor strictly greater than $\alpha_{\varphi} + \varepsilon$ would allow us to decide whether we have YES or a NO instance of the NP-hard problem $\delta$, h-ARYGAPLABELCOVER.

In order to achieve this, let us define $C^{\varphi,e} := \sum_{a \in [n] \times \{e\}} C_a^{\varphi}$. In particular, we have $C^{\varphi} = \sum_{a \in \Gamma} C_a^{\varphi} = \sum_{e \in E} C^{\varphi,e}$. For $\mathcal{T} \subseteq \mathcal{F}$, we define the relevant part of $\mathcal{T}$ on $e$ by:

$$ \mathcal{T}_e := \{T_{\beta}^{e,v} : v \in e, \beta \in [L], F_{\beta}^{v} \in \mathcal{T}\} = \{F_{\beta}^{v} \cap ([n] \times \{e\}), F_{\beta}^{v} \in \mathcal{T}\}. $$

Note that $C^{\varphi,e}(\mathcal{T}) = C^{\varphi,e}(\mathcal{T}_e)$, and in particular $C^{\varphi}(\mathcal{T}) = \sum_{e \in E} C^{\varphi,e}(\mathcal{T}_e)$.

### 3.2.2.1 Completeness

Suppose the given h-ARYLABELCOVER instance $\mathcal{G}$ is a YES instance. Then, there exists a labeling $\sigma: V \mapsto [L]$ which strongly satisfies all edges. Consider the collection of $|V|$ subsets $\mathcal{T} := \{F_{\sigma(v)}^v : v \in V\}$. Fix $e = (v_1, \dots, v_h) \in E$. Since $e$ is strongly satisfied by $\sigma$, there exists $r \in [R]$ such that $\pi_{e,v_i}(\sigma(v_i)) = r$ for all $i \in [h]$. Therefore, we get that $\mathcal{T}_e = \{T_{\sigma(v_i)}^{e,v_i}\}_{i \in [h]} = \{P_{r,i} \times \{e\}\}_{i \in [h]}$ is an $x_{\varphi}$-cover of $[n] \times \{e\}$, and so $C^{\varphi,e}(\mathcal{T}_e) = n\varphi(x_{\varphi})$. Thus $C^{\varphi}(\mathcal{T}) = \sum_{e \in E} C^{\varphi,e}(\mathcal{T}_e) = |E|\varphi(x_{\varphi})n = \varphi(x_{\varphi})|\Gamma|$.

### 3.2.2.2 Soundness

Suppose the given h-ARYLABELCOVER instance $\mathcal{G}$ is a NO instance. Let us prove the contrapositive of the soundness: we suppose that there exists $\mathcal{T}$ of size $k = |V|$ such that $C^{\varphi}(\mathcal{T}) > (\alpha_{\varphi} + \varepsilon)\varphi(x_{\varphi})|\Gamma|$. Let us show that there exists a labeling $\sigma$ that weakly satisfies a strictly larger fraction of the edges than $\delta$.

For every vertex $v \in V$, we define $L(v) := \{\beta \in [L] : F_{\beta}^v \in \mathcal{T}\}$ to be the candidate set of labels that can be associated with the vertex $v$. We extend this definition to hyperedges $e = (v_1, \dots, v_h)$ where we define $L(e) := \cup_{i \in [h]} L(v_i)$ to be the multiset of all labels associated with the edge. Note that $|\mathcal{T}_e| = |L(e)|$.

We say that $e = (v_1, \dots, v_h) \in E$ is consistent if and only if there exists $x \ne y \in [h]$ such that $\pi_{e,v_x}(L(v_x)) \cap \pi_{e,v_y}(L(v_y)) \ne \emptyset$. We then decompose $E$ in three parts:

* $B$ is the set of edges $e \in E$ with $|L(e)| \ge \frac{h}{\xi}$.

* $N$ is the set of consistent edges $e \in E$ with $|L(e)| < \frac{h}{\xi}$.

* $I = E - (B \cup N)$ is the set of inconsistent edges $e \in E$ with $|L(e)| < \frac{h}{\xi}$.

We want to show that the contribution of $N$ is not too small, which we will use to construct a labeling weakly satisfying enough edges. This comes from the following lemmas:

**Lemma 3.7.** $\sum_{e \in E} |L(e)| = |E|h$
*Proof.* Recall that our $h$-uniform hypergraph is regular; call $d$ its regular degree. In particular, we have that $d|V| = |E|h$. Note also that $\sum_{v \in V} |L(v)| = |\mathcal{T}| = |V|$. Thus:

$$ \sum_{e \in E} |L(e)| = \sum_{e \in E} \sum_{v \in V: v \in e} |L(v)| = \sum_{v \in V} \sum_{e \in E: v \in e} |L(v)| = d \sum_{v \in V} |L(v)| = d|V| = |E|h. \quad \square $$

Next, we bound the contribution of $B$:

**Lemma 3.8.** $\sum_{e \in B} C^{\varphi,e}(\mathcal{T}_e) \le \frac{\varepsilon}{4}\varphi(x_\varphi)|\Gamma|.$

*Proof.* We have:

$$ \begin{aligned} \sum_{e \in B} C^{\varphi,e}(\mathcal{T}_e) &\le \sum_{e \in B} n\varphi \left( |L(e)| \frac{x_\varphi}{h} \right) \quad \text{by remark on Definition 3.4 and } |\mathcal{T}_e| = |L(e)| \\ &\le |B| \cdot n\varphi \left( \frac{\sum_{e \in B} |L(e)|}{|B|} \frac{x_\varphi}{h} \right) \quad \text{by Jensen's inequality on concave } \varphi \\ &\le |B| \cdot n\varphi \left( \frac{|E|h}{|B|} \frac{x_\varphi}{h} \right) \\ &\quad \text{since } \varphi \text{ nondecreasing and } \sum_{e \in B} |L(e)| \le |E|h \text{ by Lemma 3.7} \\ &= \frac{\varphi\left(\frac{|E|x_\varphi}{|B|}\right)}{\frac{|E|x_\varphi}{|B|}} x_\varphi |\Gamma|. \end{aligned} \quad (3.6) $$

We have seen that $\sum_{e \in B} |L(e)| \le |E|h$, but $\sum_{e \in B} |L(e)| \ge |B| \frac{h}{\xi}$ by definition of $B$, so we have that $|B|/|E| \le \xi$. Thus $|E|x_\varphi/|B| \ge x_\varphi/\xi = \theta$. By definition of $\theta$, we get that:

$$ \sum_{e \in B} C^{\varphi,e}(\mathcal{T}_e) \le \eta x_\varphi |\Gamma| = \frac{\varepsilon}{4} \varphi(x_\varphi) |\Gamma|. \quad \square $$

In order to bound the contribution of $I$, we will prove a property on inconsistent edges:

**Proposition 3.9.** Let $e = (v_1, \dots, v_h) \in E$ be an inconsistent hyperedge with respect to $\mathcal{T}$. Then we have that $|C^{\varphi,e}(\mathcal{T}_e) - \psi_{|L(e)|,h}^{\varphi}| \le \eta n$.

*Proof.* Since $e$ is inconsistent, $\forall x \ne y \in [h]$, $\pi_{e,v_x}(L(v_x)) \cap \pi_{e,v_y}(L(v_y)) = \emptyset$. Therefore, for every $i \in [R]$, there is at most one $v \in e$ such that $i \in \pi_{e,v}(L(v))$, i.e., $\mathcal{T}_e$ intersects with $\mathcal{P}_i \times \{e\}$ in at most one subset. This gives us a subset $T \subseteq [R]$ and a function $j: T \to [h]$ such that $\mathcal{T}_e = \{P_{i,j(i)} \times \{e\} : i \in T\}$. As a consequence, $|T| = |\mathcal{T}_e| = |L(e)|$ and by the second condition of the partitioning system, we get the expected result. $\square$

Now, we can bound the contribution of $I$:

**Lemma 3.10.** $\sum_{e \in I} C^{\varphi,e}(\mathcal{T}_e) \le (\alpha_\varphi + \frac{\varepsilon}{2})\varphi(x_\varphi)|\Gamma|$.
**Proof.** Thanks to Proposition 3.9, we have:

$$ \sum_{e \in I} C^{\varphi,e}(\mathcal{T}_e) \le \sum_{e \in I} (\psi_{|L(e)|,h}^{\varphi} + \eta)n \le \sum_{e \in E} (\psi_{|L(e)|,h}^{\varphi} + \eta)n, $$

since $I \subseteq E$ and $\psi_{|L(e)|,h}^{\varphi} \ge 0$. But $\sum_{e \in E} |L(e)| = |E|h$ by Lemma 3.7 and $x \mapsto \psi_{x,h}^{\varphi}$ is concave thanks to Proposition 3.26, so we can use Jensen's inequality to get:

$$ \sum_{e \in E} \psi_{|L(e)|,h}^{\varphi} \le |E| \psi_{\sum_{e \in E} |L(e)|,h}^{\varphi} = |E| \psi_{h,h}^{\varphi}, $$

and thus:

$$ \sum_{e \in I} C^{\varphi,e}(\mathcal{T}_e) \le (\psi_{h,h}^{\varphi} + \eta)n|E| \le (\alpha_{\varphi}\varphi(x_{\varphi}) + 2\eta)|\Gamma|, $$

by definition of $h$. This implies that the total contribution of inconsistent edges $I$ is at most:

$$ \sum_{e \in I} C^{\varphi,e}(\mathcal{T}_e) \le (\alpha_{\varphi}\varphi(x_{\varphi}) + 2\eta)|\Gamma| \le (\alpha_{\varphi} + \frac{\varepsilon}{2})\varphi(x_{\varphi})|\Gamma|, $$

by definition of $\eta$.

□

**Lemma 3.11.** $\frac{|N|}{|E|} \ge \xi\eta$.

**Proof.** Since we have supposed that $\sum_{e \in E} C^{\varphi,e}(\mathcal{T}_e) = C^{\varphi}(\mathcal{T}) > (\alpha_{\varphi} + \varepsilon)\varphi(x_{\varphi})|\Gamma|$, and with the help of Lemmas 3.8 and 3.10, we have that the contribution of $N$ is:

$$ \sum_{e \in N} C^{\varphi,e}(\mathcal{T}_e) > \frac{\varepsilon}{4}\varphi(x_{\varphi})|\Gamma|. $$

However, we have that for $e \in N$ that:

$$ C^{\varphi,e}(\mathcal{T}_e) \le n\varphi\left(|\mathcal{T}_e|\frac{x_{\varphi}}{h}\right) = n\varphi\left(|L(e)|\frac{x_{\varphi}}{h}\right) \le n\varphi\left(\frac{x_{\varphi}}{\xi}\right) \le \frac{nx_{\varphi}}{\xi}, $$

thanks to the remark on Definition 3.4 and the bound $|L(e)| < \frac{h}{\xi}$. This implies that:

$$ \frac{|N|}{|E|} \ge \frac{\xi}{x_{\varphi}} \frac{\varepsilon\varphi(x_{\varphi})}{4} = \xi\eta. $$

□

Finally, we construct a randomized labeling $\sigma: V \mapsto [L]$ as follows: for $v \in V$, if $L(v) \ne \emptyset$, set $\sigma(v)$ uniformly from $L(v)$, otherwise set it arbitrarily. We claim that in expectation, this labeling must weakly satisfy $\delta$ fraction of the hyperedges.

To see this, fix any $e = (v_1, \dots, v_h) \in N$. Thus, there exists $\exists x \ne y \in [h]$ such that $\pi_{e,v_x}(L(v_x)) \cap \pi_{e,v_y}(L(v_y)) \ne \emptyset$. Furthermore $|L(v_x)|, |L(v_y)| \le \frac{h}{\xi}$. Thus, we have that $\pi_{e,v_x}(L(v_x)) = \pi_{e,v_y}(L(v_y))$ with probability at least $\frac{1}{|L(v_x)||L(v_y)|} \ge (\frac{\xi}{h})^2$. Therefore:

$$ \begin{aligned} \mathbb{E}_{\sigma} \mathbb{E}_{e \sim E}[\sigma \text{ weakly satisfies } e] &\ge \xi \eta \mathbb{E}_{\sigma} \mathbb{E}_{e \sim E}[\sigma \text{ weakly satisfies } e | e \in N] \quad \text{by Lemma 3.11} \\ &> \frac{\eta}{2} \frac{\xi^3}{h^2} = \delta. \end{aligned} \quad (3.7) $$

In particular, there exists some labeling $\sigma$ such that $\mathbb{E}_{e \sim E}[\sigma \text{ weakly satisfies } e] > \delta$, thus the soundness is proved. □
Furthermore, the previous proof implies an additive inapproximability result:

**Corollary 3.12.** *There is no additive polynomial-time approximation scheme (PTAS) for the $\varphi$-MAXCOVERAGE problem for $\varphi(n) = o(n)$ and $\alpha_\varphi < 1$ if $P \neq NP$; that is to say, a polynomial-time approximation that achieves an additive approximation error of $\varepsilon \cdot n$, with $n$ the size of the universe, for all $\varepsilon > 0$.*

*Remark.* Contrary to fully polynomial-time approximation schemes (FPTAS), a PTAS does not necessarily run in polynomial time in $\frac{1}{\varepsilon}$.

*Proof.* Let us fix $\varepsilon := \frac{1-\alpha_{\varphi}}{3}\varphi(x_{\varphi}) > 0$, which does not depend on the instance of the $\varphi$-MAXCOVERAGE problem. Assume for the sake of contradiction that we have a polynomial-time approximation that achieves an additive approximation error of $\varepsilon \cdot n$, with $n$ the size of the universe. In the previous proof (with the former $\varepsilon$ defined in Section 3.2.2 chosen equal to $\frac{1-\alpha_{\varphi}}{3}$), with such an additive approximation algorithm, one could distinguish between YES and NO instances of $\delta$, $h$-ARYGAPLABELCOVER. Indeed, a YES instance implies that the associated $\varphi$-MAXCOVERAGE instance has a solution of value $\varphi(x_{\varphi})|\Gamma|$, where $\Gamma$ is the universe in that setting. On the other hand, a NO instance implies that all solutions of the associated $\varphi$-MAXCOVERAGE instance have a value smaller than or equal to $\frac{1+2\alpha_{\varphi}}{3}\varphi(x_{\varphi})|\Gamma|$. Therefore, on a YES instance, our approximation algorithm would output a solution with a value larger than or equal to $\frac{2+\alpha_{\varphi}}{3}\varphi(x_{\varphi})|\Gamma|$. This resulting inequality is enough to guarantee that it does not come from a NO instance, as it is strictly larger than $\frac{1+2\alpha_{\varphi}}{3}\varphi(x_{\varphi})|\Gamma|$ since $\alpha_{\varphi} < 1$. Thus, such an approximation algorithm would allow us to solve $\delta$, $h$-ARYGAPLABELCOVER in polynomial time, which is impossible if $P \neq NP$. $\square$

### 3.2.3 Further Hardness Under Gap-ETH

The Gap Exponential Time Hypothesis (Gap-ETH for short) states that, for some constant $\delta > 0$, there is no $2^{o(n)}$-time algorithm that, given $n$-variable 3-SAT formula, can distinguish whether the formula is fully satisfiable or that it is not even $(1 - \delta)$-satisfiable. Gap-ETH is a standard assumption in proving FPT hardness of approximation (see e.g. [CCK$^{+}$17]). Under such hypothesis, Manurangsi showed the following theorem:

**Theorem 3.13** ([Man20], adapted to $(\delta, h)$-ARYGAPLABELCOVER). *Assuming Gap-ETH, for every $\delta > 0$, every $h \in \mathbb{N}$, $h \ge 2$ and any sufficiently large $R \in \mathbb{N}$ (depending on $\delta, h$), no $f(k) \cdot N^{o(k)}$-time algorithm can solve $(\delta, h)$-ARYGAPLABELCOVER with right alphabet $[R]$, where $k$ denotes the number of vertices in $h$-ARYLABELCOVER, $N$ is the size of the instance, and $f$ can be any function.*

Such a statement can be made in terms of the $(\delta, h)$-ARYGAPLABELCOVER problem, since it can be shown to be equivalent to $\delta$-Gap-Label-Cover$(t, R)$ (see Appendix 3.5.3 for more details).

Furthermore, in the previous reduction, the constructed instance $(\Gamma, k, \mathcal{F})$ sizes satisfy $|\Gamma| = n|E|$ (with $n$ a constant independent of the size of the instance), $k = |V|$, and $|\mathcal{F}| = k \cdot L$. Therefore, plugin Theorem 3.13 in the previous reduction leads to the following hardness result:
**Theorem 3.14.** Assuming Gap-ETH and $\varphi(n) = o(n)$, we cannot achieve an $(\alpha_{\varphi} + \varepsilon)$-approximation for the $\varphi$-MAXCOVERAGE problem, even in $f(k) \cdot m^{o(k)}$-time, for any function $f$, with $m$ the number of cover sets and $k$ the cardinality constraint.

## 3.3 Applications

In this section, we show how particular instances of $\varphi$-MAXCOVERAGE encapsulate and generalize various problems across the fields of information theory [CT01], computational social choice [BCE$^+$16] and algorithmic game theory [NRTV07].

### 3.3.1 Generalized List-Decoding

In the usual $\ell$-list-decoding problem [Eli57, Woz58], we are given a noisy channel $W(y|x)$, and the goal is to send a message chosen uniformly in $[k]$ through this channel. In order to do so, the sender encodes the input message in $\mathcal{X}$, and the receiver decodes a list of size $\ell$ of possible messages in $[k]$ from the output of the channel in $\mathcal{Y}$. The goal is to maximize the probability of successfully decoding the message, which happens when the initial message belongs to the decoded list. We consider the generalization of the $\ell$-list-decoding problem that allows decoding lists of any size, with an associated cost function $\varphi$, which we call the $\varphi$-list-decoding problem. Now, the decoding will be successful only with probability $\frac{\varphi(\ell)}{\ell}$ when the initial message belongs to a decoding list of size $\ell$. Formally, the problem can be stated as:

$$ \max_{\{L_y\}_{y \in \mathcal{Y}}, S \subseteq \mathcal{X}: |S|=k} \frac{1}{k} \sum_{x \in S} \sum_{y \in \mathcal{Y}: x \in L_y} \frac{\varphi(|L_y|)}{|L_y|} W(y|x), $$

and can be directly reformulated as:

$$ \max_{S \subseteq \mathcal{X}: |S|=k} \frac{1}{k} \sum_{y \in \mathcal{Y}} \max_{L_y \subseteq \mathcal{X}} \frac{\varphi(|L_y|)}{|L_y|} \sum_{x \in L_y} 1_{x \in S} W(y|x). $$

Let us show that with a coverage function $\varphi(j) = \min(j, \ell)$, we recover the $\ell$-list-decoding problem. Indeed, let us consider an optimal solution $S \subseteq \mathcal{X}$, $\{L_y\}_{y \in \mathcal{Y}}$ of the $\varphi$-list-decoding, with $L_y$ the list of accepted messages when the output of the channel is $y$. If all lists $L_y$ are of size $\ell$, then as $\frac{\varphi(\ell)}{\ell} = 1$, we recover a solution of the $\ell$-list-decoding problem with the same objective value. This shows in particular that the $\varphi$-list-decoding problem has an objective optimal value at least as large as the usual $\ell$-list-decoding problem. Let us now consider an arbitrary set $\{L_y\}_{y \in \mathcal{Y}}$, and let us look at a particular list $L_y$ with $L_y \neq \ell$. Let us show that we can efficiently build another list of size $\ell$ while keeping a solution with an objective value at least as good as with $L_y$. If $|L_y| \le \ell$, then $\frac{\varphi(|L'_y|)}{|L'_y|} = 1$. Therefore, adding elements in $L_y$ can only increase the objective value, as long as we keep $\frac{\varphi(|L_y|)}{|L_y|} = 1$, i.e. that the list size is smaller than or equal to $\ell$. Thus, we can transform all the lists $L_y$ with $|L_y| < \ell$ into lists of size $\ell$ without decreasing the value of that solution. If $|L_y| > \ell$, then $\frac{\varphi(|L_y|)}{|L_y|} = \frac{\ell}{|L_y|}$. We will keep only the $\ell$ most influencing messages in $L_y$ and we will show that it does not decrease the objective value. Specifically, let us sort the elements $x \in L_y$ in a nonincreasing order according to $1_{x \in S} W(y|x)$ and keep the first $\ell$ elements of that list. We call $L'_y$ the resulting list. We claim that replacing $L_y$ by $L'_y$ will not decrease the
objective value. Indeed, we have:

$$ \sum_{x \in L'_y} \mathbb{1}_{x \in S} W(y|x) \geq \frac{\ell}{|L'_y|} \sum_{x \in L_y} \mathbb{1}_{x \in S} W(y|x), $$

as $L'_y$ contains the $\ell$ largest elements of $L_y$ according to the weight $\mathbb{1}_{x \in S} W(y|x)$. Therefore, since $\frac{\varphi(|L'_y|)}{|L'_y|} = 1$, we have:

$$ \frac{\varphi(|L'_y|)}{|L'_y|} \sum_{x \in L'_y} \mathbb{1}_{x \in S} W(y|x) \geq \frac{\varphi(|L_y|)}{|L_y|} \sum_{x \in L_y} \mathbb{1}_{x \in S} W(y|x), $$

thus replacing $L_y$ by $L'_y$ does not decrease the objective value. This concludes the equivalence of the $\ell$-list-decoding problem with the $\varphi$-list-decoding with $\varphi(j) = \min(j, \ell)$.

When the channel is of the form $W(y|x) = \frac{1}{t}$ for $y \in T_x$ with $|T_x| = t$ and $W(y|x) = 0$ elsewhere, the success probability of the $\varphi$-list-decoding problem for a code $S \subseteq \mathcal{X}$ can be written as $\frac{1}{kt} \sum_{y \in \mathcal{Y}} \varphi(|S_y|)$, with $S_y := \{x \in S : y \in T_x\}$, which is a particular instance of the $\varphi$-MAXCOVERAGE problem. Indeed, for a fixed code $S$, the objective value becomes:

$$ \begin{aligned} \frac{1}{k} \sum_{y \in \mathcal{Y}} \max_{L_y \subseteq \mathcal{X}} \frac{\varphi(|L_y|)}{|L_y|} \sum_{x \in L_y} \mathbb{1}_{x \in S} W(y|x) &= \frac{1}{kt} \sum_{y \in \mathcal{Y}} \max_{L_y \subseteq \mathcal{X}} \frac{\varphi(|L_y|)}{|L_y|} \sum_{x \in L_y} \mathbb{1}_{x \in S} \mathbb{1}_{y \in T_x} \tag{3.8} \\ &= \frac{1}{kt} \sum_{y \in \mathcal{Y}} \max_{L_y \subseteq \mathcal{X}} \frac{\varphi(|L_y|)}{|L_y|} |S_y \cap L_y|. \end{aligned} $$

We will show that $\max_{L_y \subseteq \mathcal{X}} \frac{\varphi(|L_y|)}{|L_y|} |S_y \cap L_y| = \varphi(|S_y|)$, which will prove the claimed rewriting of the $\varphi$-list-decoding for those particular channels. As $\varphi(0) = 0$ and $\varphi$ is concave, we have for all $y \geq x \geq 0$:

$$ \frac{\varphi(y) - \varphi(0)}{y - 0} \leq \frac{\varphi(x) - \varphi(0)}{x - 0}, $$

i.e. $\frac{x}{y}\varphi(y) \leq \varphi(x)$. Therefore, we have that:

$$ \frac{\varphi(|L_y|)}{|L_y|} |S_y \cap L_y| \leq \varphi(|S_y \cap L_y|) \leq \varphi(|S_y|), $$

as $\varphi$ is nondecreasing. Thus, $\max_{L_y \subseteq \mathcal{X}} \frac{\varphi(|L_y|)}{|L_y|} |S_y \cap L_y| \leq \varphi(|S_y|)$, with the equality obtained by choosing $L_y := S_y$.

Therefore, for that class of channels, a tight approximation ratio $\alpha_{\varphi}$ follows from Theorem 3.1. As a consequence, the hardness part holds for the general $\varphi$-list-decoding problem, whereas finding an approximation algorithm achieving the ratio $\alpha_{\varphi}$ for all channels is left as an open question.

### 3.3.2 Multiwinner Elections

As mentioned previously, multiwinner elections (with a utilitarian model for the voters) entail selection of $k$ (out of $m$) candidates that maximize the utility across $n$ voters. Here,
the utility of each voter $a \in [n]$ increases with the number of approved (by a) selections. The work of Dudycz et al. [DMMS20] study the computational complexity of such elections and, in particular, address classic voting rules in which—for a specified sequence of nonnegative weights $(w_1, w_2, \ldots)$—voter a’s utility is equal to $\sum_{i=1}^j w_i$, when he approves of j candidates among the selected ones. One can view this election exercise as a coverage problem by considering subset $T_i \subseteq [n]$ as the set of voters that approve of candidate $i \in [m]$ and $\varphi(j) = \sum_{i=1}^j w_i$. Indeed, for a subset of candidates $S \subseteq [m]$, the utility of a voter $a \in [n]$ is equal to $\varphi(|S|_a)$, with $|S|_a = |\{i \in S : a \in T_i\}|$.

Dudycz et al. [DMMS20] show that if the weights satisfy $w_1 \ge w_2 \ge \ldots$ (i.e., bear a diminishing returns property) along with geometric dominance ($w_i \cdot w_{i+2} \ge w_{i+1}^2$ for all $i \in \mathbb{N}^*$) and $\lim_{i \to \infty} w_i = 0$, then a tight approximation guarantee can be obtained for the election problem at hand. Note that the diminishing returns property implies that $\varphi(j) = \sum_{i=1}^j w_i$ is concave and $\lim_{i \to \infty} w_i = 0$ ensures that $\varphi$ is sublinear (see Proposition 3.27). Hence, Theorem 3.1, together with Proposition 3.28, can be invoked to recover the result in [DMMS20] where we get $\alpha_\varphi = \alpha_\varphi(1)$. In fact, Theorem 3.1 does not require geometric dominance among the weights and, hence, applies to a broader class of voting rules. For instance, the geometric dominance property does not hold if one considers the voting weights induced by $\ell$-MULTI COVERAGE, i.e., $w_i = 1$, for $1 \le i \le \ell$, and $w_j = 0$ for $j > \ell$. However, using Theorem 3.1, we get that for this voting rule we can approximate the optimal utility within a factor of $\alpha_\varphi = 1 - \frac{\ell^\ell e^{-\ell}}{\ell!}$ (see Proposition 3.31). Another example of such a separation arises if one truncates the proportional approval voting. The standard proportional approval voting corresponds to $w_i = \frac{1}{i}$, for all $i \in \mathbb{N}$ (equivalently, $\varphi(j) = \sum_{i=1}^j \frac{1}{i}$) and falls within the purview of [DMMS20]. While the truncated version with $\varphi(j) = \sum_{i=1}^{\min(j, \ell)} \frac{1}{i}$, for a given threshold $\ell$, does not satisfy geometric dominance, Theorem 3.1 continues to hold and provide a tight approximation ratio that can be computed numerically (see Proposition 3.21 and Table 3.1 for examples).

### 3.3.3 Resource Allocation in Multi-Agent Systems

A significant body of prior work in algorithmic game theory has addressed game-theoretic aspects of maximizing welfare among multiple (strategic) agents; see, e.g., [PM18]. Completing such results, this section shows that the optimization problem underlying multiple welfare-maximization games can be expressed in terms of $\varphi$-MAXCOVERAGE.

Specifically, consider a setting with $n$ resources, $k$ agents, and a function $\varphi : \mathbb{N} \mapsto \mathbb{R}_+$. Every agent $i$ is endowed with a collection of resource subsets $A_i = \{T_1^i, \ldots, T_{m_i}^i\} \subseteq 2^{[n]}$ (i.e., each $T_j^i \subseteq [n]$). The objective is to select a subset $A_i \in A_i$, for all $i \in [k]$, so as to maximize $W\varphi(A_1, A_2, \ldots, A_k) := \sum_{a \in [n]} w_a \varphi(|A_a|)$. Here, $w_a \in \mathbb{R}_+$ is a weight associated with $a \in [n]$ and $|A_a| := |\{i \in [k] : a \in A_i\}|$. We will refer to this problem as the $\varphi$-RESOURCE ALLOCATION problem.

While $\varphi$-RESOURCE ALLOCATION does not directly reduce to $\varphi$-MAXCOVERAGE, the next theorem shows that it corresponds to maximizing $\varphi$-coverage functions subject to a matroid constraint. Hence, invoking our result from Section 3.1.1, we obtain a tight $\alpha_\varphi$-approximation for $\varphi$-RESOURCE ALLOCATION (see Appendix 3.5.5 for the proof):

**Theorem 3.15.** For any normalized nondecreasing concave function $\varphi$, there exists a $\alpha_\varphi$-approximation algorithm for $\varphi$-RESOURCE ALLOCATION running in polynomial time. Further-
more, for $\varphi(n) = o(n)$, it is NP-hard to approximate $\varphi$-RESOURCE ALLOCATION within a factor better than $\alpha_{\varphi} + \varepsilon$, for any constant $\varepsilon > 0$.

### 3.3.4 Vehicle-Target Assignment

VEHICLE-TARGET ASSIGNMENT [Mur00, PM18] is another problem which highlights the applicability of coverage problems, with a concave $\varphi$. In particular, VEHICLE-TARGET ASSIGNMENT can be directly expressed as $\varphi$-RESOURCE ALLOCATION: the $[n]$ resources correspond to targets, the agents correspond to vehicles $i \in [k]$, each with a collection of covering choices $A_i \subseteq 2^{[n]}$, and $\varphi^p(j) = \frac{1-(1-p)^j}{p}$, for a given parameter $p \in (0, 1)$. As limit cases, we define $\varphi^0(j) := \lim_{p \to 0} \varphi^p(j) = j$ and $\varphi^1(j) := 1$. Since $\varphi^p(j)$ is concave, by Proposition 3.32 and Theorem 3.15, we obtain a novel tight approximation ratio of $\alpha_{\varphi^p} = \frac{1-e^{-p}}{p}$ for this problem. Also, one can look at the capped version of this problem, $\varphi_{\ell}^p(j) := \varphi^p(\min(j, \ell))$. In particular, we recover the $\ell$-MULTI COVERAGE function when $p=0$. In Figure 3.1, we have plotted several cases of the tight approximations $\alpha_{\varphi_{\ell}^p}$ in function of $\ell$ for several values of $\ell$:

<figure><img src="image_5.png" /><figcaption>Figure 3.1 – Tight approximation ratios $\alpha_{\varphi_{\ell}^p}$, where $\ell$ is the rank of the capped version of the $p$-VEHICLE-TARGET ASSIGNMENT problem. When $p=0$, we recover the $\ell$-coverage problem.</figcaption></figure>

Paccagnan and Marden [PM18] study the game-theoretic aspects of VEHICLE-TARGET ASSIGNMENT. A key goal in [PM18] is to bound the welfare loss incurred due to strategic selection by the $k$ vehicles, i.e., the selection of each $A_i \in A_i$ by a self-interested vehicle/agent $i \in [k]$. The loss is quantified in terms of the *Price of Anarchy* (PoA). Formally, this performance metric is defined as ratio between the welfare of the worst-possible equilibria and the optimal welfare. Paccagnan and Marden [PM18] show that, for computationally tractable equilibrium concepts (in particular, for coarse correlated equilibria), tight price of anarchy bounds can be obtained via linear programs.

Note that our hardness result (Theorem 3.1) provides upper bounds on PoA of tractable equilibrium concepts–this follows from the observation that computing an equilibrium provides a specific method for finding a coverage solution. In [CPM19] and in the partic-
ular case of the *-MULTI COVERAGE problem, it is shown that this in fact an equality, i.e.,
PoA = α_φ if φ(j) = min(j, ℓ) for all values of ℓ. However, numerically comparing the
approximation ratio for VEHICLE-TARGET ASSIGNMENT, α_φ^p = (1-e^{-p})/p, with the optimal
PoA bound, we note that α_φ^p can in fact be strictly greater than the PoA guarantee; see
Figure 3.2.

Another form of the current problem, considered in [PM18], corresponds to $\varphi^d(j) = j^d$, for a given parameter $d \in (0, 1)$. We refer to this instantiation as the $d$-POWER function and for it obtain the approximation ratio $\alpha_{\varphi^d} = e^{-1} \sum_{k=1}^{+\infty} \frac{k^d}{k!}$ (Proposition 3.33). In this case, the question whether the inequality $\text{PoA} \le \alpha_{\varphi}$ is tight remains open; see Figure 3.3.

<figure><img src="image_6.png" /><figcaption>Figure 3.2 – Comparison between the PoA and α_φ for the VEHICLE-TARGET ASSIGNMENT problem. Using the linear program found in [PM18], we were able to compute the blue curve PoA^20, the *Price of Anarchy* of this problem for *m* = 20 players. Since the PoA only decreases when the number of players grows, this means that PoA < α_φ in that case. As a comparison, the red curve Curv depicts the general approximation ratio (see [SVW17]) obtained for submodular function with curvature *c*, with *c* = 1 - φ^p(*m*) + φ^p(*m* - 1) here.</figcaption></figure>

**3.3.5 Welfare Maximization for φ-Coverage**

Maximizing (social) welfare by partitioning items among agents is a key problem in algo-
rithmic game theory; see, e.g., the extensive work on combinatorial auctions [NRTV07].
The goal here is to partition *t* items among a set of *k* agents such that the sum of values
achieved by the agents—referred to as the social welfare—is maximized. That is, one needs
to partition [*t*] into *k* pairwise disjoint subsets *A*₁, *A*₂, . . . , *A*ₖ with the objective of max-
imizing ∑<sub>*i*=<1</sub><sup>*k*</sup> *v*ᵢ(*A*ᵢ). Here, *v*ᵢ(*S*) denotes the valuation that agent *i* has for a subset of
items *S* ⊆ [*t*].

When each agent's valuation $v_i$ is submodular, a tight $(1 - e^{-1})$-approximation ratio is known for social welfare maximization [Von07]. This section shows that improved approximation guarantees can be achieved if, in particular, the agents' valuations are $\varphi$-coverage functions. Towards a stylized application of such valuations, consider a setting in which each "item" $b \in [t]$ represents a bundle (subset) of goods $T_b \subseteq [n]$ and the value of
<figure><img src="image_7.png" /><figcaption>Figure 3.3 – Comparison between the PoA and $\alpha_{\varphi}$ for the $d$-POWER problem. Using the linear program found in [PM18], we were able to compute the blue curve PoA$^{20}$, the *Price of Anarchy* of this problem for $m = 20$ players. Here, the question whether the inequality $\text{PoA} \le \alpha_{\varphi}$ is tight remains open. As a comparison, the red curve Curv depicts the general approximation ratio (see [SVW17]) obtained for submodular function with curvature $c$, with $c = 1 - \varphi^d(m) + \varphi^d(m-1)$ here.</figcaption></figure>

an agent increases with the number of copies of any good $a \in [n]$ that get accumulated. Indeed, if each agent's value for $j$ copies of a good is $\varphi(j)$, then we have a $\varphi$-coverage function and the overall optimization problem is find a $k$-partition, $A_1, A_2, \dots, A_k$, of $[t]$ that maximizes $\sum_{i=1}^k (\sum_{a \in [n]} \varphi(|A_i|_a))$, where $|A_i|_a := \{b \in A_i : a \in T_b\}$.

In the current setup, one can obtain an $\alpha_{\varphi}$ approximation ratio for social-welfare maximization by reducing this problem to $\varphi$-coverage with a matroid constraint, and applying the result from Section 3.1.1. Specifically, we can consider a partition matroid over the universe $[t] \times [k]:$ for a bundle/item $b \in [t]$ and an agent $i \in [k]$, the element $(b, i)$ in the universe represents that bundle $b$ is assigned to agent $i$, i.e., $b \in A_i$. The partition-matroid constraint is imposed to ensure that each bundle $b$ is assigned to at most one agent. Furthermore, we can create $k$ copies of the underlying set of goods $[n]$ and set $T_{(b,i)} := \{(a, i) : a \in T_b\}$ to map the $\varphi$-coverage over the universe to the social-welfare objective. This, overall, gives us the desired $\alpha_{\varphi}$ approximation guarantee.

## 3.4 Conclusion

We have introduced the $\varphi$-MAXCOVERAGE problem where having $c$ copies of element $a$ gives a value $\varphi(c)$. 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(\text{Poi}(x))]}{\varphi(\mathbb{E}[\text{Poi}(x)])}$ and we showed it is tight for sublinear functions $\varphi$. The Poisson concavity ratio strictly beats the bound one gets using the notion of curvature of submodular functions, except in limit cases such as MAXCOVERAGE where the bounds are equal.

An interesting open question is whether there exists combinatorial algorithms that achieve
this approximation ratio. As mentioned in [BFGG20], for the $\ell$-MULTICOVERAGE with $\ell \ge 2$, which is the special case where $\varphi(x) = \min(x, \ell)$, the simple greedy algorithm only gives a $1 - e^{-1}$ approximation ratio, which is strictly less than the ratio $\alpha_{\varphi} = 1 - \frac{\ell e^{-\ell}}{\ell!}$ in that case. Also, for any geometrically dominant vector $w = (\varphi(i+1) - \varphi(i))_{i \in \mathbb{N}}$ which is not $p$-geometric, such as PROPORTIONAL APPROVAL VOTING, the greedy algorithm achieves an approximation ratio which is strictly less than $\alpha_{\varphi}$ (see Theorem 18 of [DMMS20]).

Another open question is whether the hardness result remains true when $\varphi(n) \ne o(n)$. A good example is given by $\varphi(0) = 0$ and $\varphi(1+t) = 1+(1-c)t$ with $c \in (0, 1)$. We know that the problem is hard for $c=1$ but easy for $c=0$. One can show that the approximation ratio achieved by our algorithm is $\alpha_{\varphi} = 1 - \frac{c}{e}$ in that case (which is the same approximation ratio obtained from the curvature in [SVW17]), but the tightness of this approximation ratio remains open.
## 3.5 Appendix

### 3.5.1 General Properties

In this section, we will assume that $\varphi$ is specified over nonnegative integers (i.e. $\varphi: \mathbb{N} \to \mathbb{R}_+$) and that it is nondecreasing, concave, and normalized (i.e. $\varphi(0) = 0$ and $\varphi(1) = 1$). We will consider its piecewise linear extension on $\mathbb{R}_+$ by defining $\varphi(x) := \lambda\varphi(|x|) + (1-\lambda)\varphi(\lceil x \rceil)$; here, parameter $\lambda \in [0, 1]$ satisfies $x = \lambda|x| + (1-\lambda)\lceil x \rceil$. Note that the piecewise linear extension is also nondecreasing and concave.

**Proposition 3.16.** For all $x \in \mathbb{R}_+$, we have $\alpha_{\varphi}(x) \ge \min(\alpha_{\varphi}(|x|), \alpha_{\varphi}(\lceil x \rceil))$; here, $\alpha_{\varphi}(0) := \lim_{x \to 0} \alpha_{\varphi}(x) = 1$.

*Proof.* For any $x \ge 1$, consider parameter $\lambda \in [0, 1]$ such that $x = \lambda|x| + (1-\lambda)\lceil x \rceil$. Since $x \mapsto \mathbb{E}[\varphi(\mathrm{Poi}(x))]$ is concave (Proposition 3.25), the following bound holds for all $x \ge 1$:

$$ 
\begin{aligned}
\mathbb{E}[\varphi(\mathrm{Poi}(x))] &\ge \lambda \mathbb{E}[\varphi(\mathrm{Poi}(|x|))] + (1-\lambda)\mathbb{E}[\varphi(\mathrm{Poi}(\lceil x \rceil))] \\
&= \lambda \alpha_{\varphi}(|x|)\varphi(|x|) + (1-\lambda)\alpha_{\varphi}(\lceil x \rceil)\varphi(\lceil x \rceil) \quad \text{by definition of } \alpha_{\varphi}(x) \\
&\ge \min(\alpha_{\varphi}(|x|), \alpha_{\varphi}(\lceil x \rceil)) (\lambda\varphi(|x|) + (1-\lambda)\varphi(\lceil x \rceil)) \\
&= \min(\alpha_{\varphi}(|x|), \alpha_{\varphi}(\lceil x \rceil))\varphi(x),
\end{aligned} 
\quad (3.9) $$

since $\varphi$ linear between integers. Therefore, $\alpha_{\varphi}(x) = \frac{\mathbb{E}[\varphi(\mathrm{Poi}(x))]}{\varphi(x)} \ge \min(\alpha_{\varphi}(|x|), \alpha_{\varphi}(\lceil x \rceil))$.

We will show next that $\alpha_{\varphi}(x)$ is nonincreasing from 0 to 1, which implies that for $x \in [0, 1)$, we have $\alpha_{\varphi}(x) \ge \min(\alpha_{\varphi}(|x|), \alpha_{\varphi}(\lceil x \rceil))$. Since $\varphi$ is linear between integers, $\varphi(0) = 0$ and $\varphi(1) = 1$, we have that $\varphi(x) = x$ for all $x \in [0, 1]$. Therefore:

$$ \alpha_{\varphi}(x) = \frac{\mathbb{E}[\varphi(\mathrm{Poi}(x))]}{x} = e^{-x} \sum_{k=1}^{+\infty} \frac{\varphi(k)}{k} \frac{x^{k-1}}{(k-1)!} = e^{-x} \sum_{k=0}^{+\infty} \frac{\varphi(k+1)}{k+1} \frac{x^k}{k!}. $$

In particular, $\alpha_{\varphi}(x)$ is well-defined at 0 and $\alpha_{\varphi}(0) = e^{-0} \sum_{k=0}^{+\infty} \frac{\varphi(k+1)}{k+1} \frac{0^k}{k!} = 1$. Now, consider the derivative:

$$ 
\begin{aligned}
\alpha'_{\varphi}(x) &= e^{-x} \left( - \sum_{k=0}^{+\infty} \frac{\varphi(k+1)}{k+1} \frac{x^k}{k!} + \sum_{k=1}^{+\infty} \frac{\varphi(k+1)}{k+1} \frac{x^{k-1}}{(k-1)!} \right) \\
&= e^{-x} \sum_{k=0}^{+\infty} \left( \frac{\varphi(k+2)}{k+2} - \frac{\varphi(k+1)}{k+1} \right) \frac{x^k}{k!}.
\end{aligned} 
\quad (3.10) $$

Note that $\frac{\varphi(k+2)}{k+2} - \frac{\varphi(k+1)}{k+1} = \frac{\varphi(k+2)-\varphi(0)}{(k+2)-0} - \frac{\varphi(k+1)-\varphi(0)}{(k+1)-0} \le 0$; the last inequality follows from the concavity of $\varphi$. Hence, $\alpha'_{\varphi}(x) \le 0$. That is, $\alpha_{\varphi}(x)$ is nonincreasing from 0 to 1. $\square$

**Proposition 3.17.** For any $\varepsilon > 0$, the bound $1 - \alpha_{\varphi}(x) \le \varepsilon$ holds for all $x \ge (\frac{6}{\varepsilon})^4$.

*Proof.* Write $X \sim \mathrm{Poi}(x)$ and note that $\mathrm{P}(X \le x(1-\delta(x))) \le \exp(-\frac{x\delta(x)^2}{2(1+\delta(x))})$, for any positive function $\delta(\cdot)$ which satisfies $\delta(x) < 1$, for all $x > 1$; see for instance [Can17].
Therefore:

$$
\begin{align*}
\mathbb{E}[\varphi(X)] &\ge e^{-x} \sum_{k=\lfloor x(1-\delta(x)) \rfloor}^{+\infty} \varphi(k) \frac{x^k}{k!} \quad \text{since } \varphi \text{ nonnegative} \\
&\ge \varphi(x(1-\delta(x))) \sum_{k=\lfloor x(1-\delta(x)) \rfloor}^{+\infty} e^{-x} \frac{x^k}{k!} \quad \text{since } \varphi \text{ nondecreasing} \tag{3.11} \\
&\ge \varphi(x(1-\delta(x)))(1-\mathbb{P}(X \le x(1-\delta(x)))) \\
&\ge \varphi(x(1-\delta(x))) \left(1 - \exp\left(-\frac{x\delta(x)^2}{2(1+\delta(x))}\right)\right).
\end{align*}
$$

Next, we will show that $\frac{\varphi(x(1-\delta(x)))}{\varphi(x)} \ge 1 - \frac{\delta(x)+\frac{1}{x}}{1-\delta(x)}$. Towards this end, we will first bound $\varphi(x+y)-\varphi(x)$ in terms of $w_k^x = \varphi(x+k)-\varphi(x+k-1)$, which constitutes a nonincreasing sequence (since $\varphi$ is concave):

$$
\varphi(x + y) - \varphi(x) \le \varphi(x + \lfloor y \rfloor + 1) - \varphi(x + \lfloor y \rfloor) + \sum_{k=1}^{\lfloor y \rfloor} w_k^x \le (\lfloor y \rfloor + 1) w_1^x.
$$

Applying this bound to $x(1 - \delta(x))$ and $x\delta(x)$ gives us:

$$
\begin{align*}
1 - \frac{\varphi(x(1-\delta(x)))}{\varphi(x)} &= \frac{\varphi(x) - \varphi(x(1-\delta(x)))}{\varphi(x)} \le \frac{(|x\delta(x)| + 1)w_1^{x(1-\delta(x))}}{\varphi(x)} \\
&\le \frac{x\delta(x) + 1}{\varphi(x)} \frac{\varphi(x(1-\delta(x)))}{x(1-\delta(x))} \le \frac{x\delta(x) + 1}{x(1-\delta(x))} = \frac{\delta(x) + \frac{1}{x}}{1-\delta(x)}. \quad (3.12)
\end{align*}
$$

Here, $w_1^{x(1-\delta(x))} = \frac{\varphi(x(1-\delta(x))+1)-\varphi(x(1-\delta(x)))}{(x(1-\delta(x))+1)-(x(1-\delta(x)))} \le \frac{\varphi(x(1-\delta(x)))-\varphi(0)}{x(1-\delta(x))-0} = \frac{\varphi(x(1-\delta(x)))}{x(1-\delta(x))}$ follows
from the concavity of $\varphi$ and $\frac{\varphi(x(1-\delta(x)))}{\varphi(x)} \le 1$ from the fact that $\varphi$ is nondecreasing.

Inequalities (3.11) and (3.12) lead to following upper bound on $1 - \alpha_{\varphi}(x)$ in terms of $\delta(x)$:

$$
\begin{align}
1 - \alpha_{\varphi}(x) &= 1 - \frac{\mathbb{E}[\varphi(\mathrm{Poi}(x))]}{\varphi(x)} \le 1 - \left(1 - \frac{\delta(x) + \frac{1}{x}}{1 - \delta(x)}\right) \left(1 - \exp\left(-\frac{x\delta(x)^2}{2(1 + \delta(x))}\right)\right) \nonumber \\
&\le \frac{\delta(x) + \frac{1}{x}}{1 - \delta(x)} + \exp\left(-\frac{x\delta(x)^2}{2(1 + \delta(x))}\right). \tag{3.13}
\end{align}
$$

Specifically setting $\delta(x) = x^{-1/4}$, we have (for all $x \ge 16$): $\delta(x) \le 1/2$, $1/x \le x^{-1/4}$, and
$\exp(-x\delta(x)^2/2(1+\delta(x))) \le \exp(-\sqrt{x}/4) \le 2x^{-1/4}$. Hence, inequality (3.13) reduces to

$$
1 - \alpha_{\varphi}(x) \le \frac{2x^{-\frac{1}{4}}}{1 - \frac{1}{2}} + 2x^{-\frac{1}{4}} \le 6x^{-\frac{1}{4}} \quad \text{for all } x \ge 16.
$$

If $\varepsilon \ge 1$, we have $1 - \alpha_{\varphi}(x) \le 1 \le \varepsilon$. Otherwise, we have that $(\frac{6}{\varepsilon})^4 \ge 6^4 \ge 16$. Therefore, given any $\varepsilon > 0$, for all $x \ge (\frac{6}{\varepsilon})^4$ we have $1 - \alpha_{\varphi}(x) \le \varepsilon$. $\square$
**Proposition 3.18.** We have that $\alpha_{\varphi} = \inf_{x \in \mathbb{R}_+} \alpha_{\varphi}(x) = \min_{x \in \mathbb{N}^*} \alpha_{\varphi}(x)$.

*Proof.* Thanks to Proposition 3.16, we have that $\inf_{x \in \mathbb{R}_+} \alpha_{\varphi}(x) = \inf_{x \in \mathbb{N}^*} \alpha_{\varphi}(x)$, and thanks to Proposition 3.17, since $\alpha_{\varphi}(x) \le 1$, we have that $\inf_{x \in \mathbb{N}^*} \alpha_{\varphi}(x) = \min_{x \in \mathbb{N}^*} \alpha_{\varphi}(x)$. $\square$

**Proposition 3.19.** $C^{\varphi}$ is submodular, its curvature is at most $c = 1 - (\varphi(m) - \varphi(m-1))$ and it cannot be improved for a general instance with $m$ cover sets.

*Proof.* We will use the following straightforward lemma:

**Lemma 3.20** (Properties of $|S|_a = |\{i \in S : a \in T_i\}|$). We have:

1. $|S|_a \le |S|_a$,

2. $|S \cup S'|_a \le |S|_a + |S'|_a$. If $S \subseteq T$ then $|S|_a \le |T|_a$ and $|S \cup \{x\}|_a \le |S|_a + 1$,

3. If $S \subseteq T$, $x \notin T$ then $|S|_a = |T|_a \Rightarrow |S \cup \{x\}|_a = |T \cup \{x\}|_a$.

Let us show first the submodularity of $C^{\varphi}$. Let $S \subseteq T \subseteq [m]$ and $x \notin T$:

$$C^{\varphi}(S \cup \{x\}) - C^{\varphi}(S) - (C^{\varphi}(T \cup \{x\}) - C^{\varphi}(T)) = \\ = \sum_{a \in [n]} w_a[\varphi(|S \cup \{x\}|_a) - \varphi(|S|_a) - (\varphi(|T \cup \{x\}|_a) - \varphi(|T|_a))] . \quad (3.14)$$

Let us call $g(a) := \varphi(|S \cup \{x\}|_a) - \varphi(|S|_a) - (\varphi(|T \cup \{x\}|_a) - \varphi(|T|_a))$:

1. If $|T|_a = |S|_a$ then thanks to Lemma 3.20, we have that $|T \cup \{x\}|_a = |S \cup \{x\}|_a$, so $g(a) = 0$

2. Else, we have that $|T|_a > |S|_a$:

a) If $|S \cup \{x\}|_a = |S|_a$, then we add elements of $T - S$ using Lemma 3.20 to get that $|T \cup \{x\}|_a = |T|_a$, so $g(a) = 0$ in that case.

b) Else $|S \cup \{x\}|_a \ne |S|_a$. So with $|S|_a = k$, we get that $|S \cup \{x\}|_a = k + 1$ and $|T|_a > |S|_a$ so $|T|_a \ge k + 1$.

i. If $|T \cup \{x\}|_a = |T|_a$, then $g(a) = \varphi(k+1) - \varphi(k) \ge 0$ since $\varphi$ is nondecreasing.

ii. Else $|T \cup \{x\}|_a \ne |T|_a$ so with $|T|_a = \ell$ with $\ell \ge k + 1$, we get that $|T|_a = \ell + 1$. So we have that:

$$g(a) = \varphi(k+1) - \varphi(k) - (\varphi(\ell+1) - \varphi(\ell)) \\ = \frac{\varphi(k+1) - \varphi(k)}{(k+1)-k} - \frac{\varphi(\ell+1) - \varphi(\ell)}{(\ell+1)-\ell} \ge 0, \quad (3.15)$$

by concavity of $\varphi$: its slopes are nonincreasing.
So in all cases, we have $g(a) \ge 0$ so $C^{\varphi}(S \cup \{x\}) - C^{\varphi}(S) - (C^{\varphi}(T \cup \{x\}) - C^{\varphi}(T)) \ge 0$:
$C^{\varphi}$ is submodular.

Let us now compute its curvature:

$$c = 1 - \min_{i \in [m]} \frac{C^{\varphi}([m]) - C^{\varphi}([m] - \{i\})}{C^{\varphi}(\{i\}) - C^{\varphi}(\emptyset)}.$$

Let $i \in [m]$ fixed:

$$\begin{align*}
\frac{C^{\varphi}([m]) - C^{\varphi}([m] - \{i\})}{C^{\varphi}(\{i\}) - C^{\varphi}(\emptyset)} &= \frac{\sum_{a \in [n]} w_a[\varphi(|[m]|_a) - \varphi(|[m] - \{i\}|_a)]}{\sum_{a \in [n]} w_a[\varphi(|\{i\}|_a) - \varphi(|\emptyset|_a)]} \\
&= \frac{\sum_{a \in T_i} w_a[\varphi(|[m]|_a) - \varphi(|[m] - \{i\}|_a)]}{\sum_{a \in T_i} w_a} \tag{3.16} \\
&= \frac{\sum_{a \in T_i} w_a[\varphi(|[m]|_a) - \varphi(|[m]|_a - 1)]}{\sum_{a \in T_i} w_a},
\end{align*}$$

since $a \in T_i$. But $|[m]|_a \le m$ and $\varphi$ concave, so $\varphi([m]|_a) - \varphi([m]|_a - 1) \ge \varphi(m) - \varphi(m-1)$ for all $a \in [n]$. As a consequence we have that:

$$\frac{C^{\varphi}([m]) - C^{\varphi}([m] - \{i\})}{C^{\varphi}(\{i\}) - C^{\varphi}(\emptyset)} \ge \varphi(m) - \varphi(m-1),$$

and this lower bound is true for its minimum over $i$. Thus we get that $c \le 1 - (\varphi(m) - \varphi(m-1))$. Also one can find instances for all $m$ such that this bound is tight: take $T_1 = \{a\}$ and $\forall j \in [m], a \in T_j$ for instance. $\square$

**Proposition 3.21.** Let $\ell \in \mathbb{N}^*$. if $\forall x \ge \ell$, $\varphi(x) = \varphi(\ell) + a(x - \ell)$ for some $0 \le a \le \varphi(\ell) - \varphi(\ell - 1)$, then $\alpha_{\varphi}(x)$ is nondecreasing from $\ell$ to $+\infty$ and:

$$\alpha_{\varphi}(x) = \frac{\varphi(\ell) + a(x - \ell)}{\varphi(x)} - \frac{e^{-x}}{\varphi(x)} \left( \sum_{k=0}^{\ell} (\varphi(\ell) + a(x - \ell) - \varphi(k)) \frac{x^k}{k!} - a \frac{x^{\ell+1}}{\ell!} \right).$$

In particular, $\alpha_{\varphi} = \min_{x \in [\ell]} \alpha_{\varphi}(x)$, and the argmin can be computed numerically.

*Proof.* One can compute a closed form value for $\alpha_{\varphi}(x)$ using the fact that $\varphi$ is linear from $\ell$:

$$\begin{align}
\alpha_{\varphi}(x) &= \frac{e^{-x}}{\varphi(x)} \sum_{k=0}^{+\infty} \varphi(k) \frac{x^k}{k!} = \frac{e^{-x}}{\varphi(x)} \left( \sum_{k=0}^{\ell} \varphi(k) \frac{x^k}{k!} + \sum_{k=\ell+1}^{+\infty} (\varphi(\ell) + a(k-\ell)) \frac{x^k}{k!} \right) \nonumber \\
&= \frac{\varphi(\ell) - a\ell}{\varphi(x)} + \frac{e^{-x}}{\varphi(x)} \left( \sum_{k=0}^{\ell} (\varphi(k) - \varphi(\ell) + a\ell) \frac{x^k}{k!} + ax \sum_{k=\ell+1}^{+\infty} \frac{x^{k-1}}{(k-1)!} \right) \nonumber \\
&= \frac{\varphi(\ell) + a(x-\ell)}{\varphi(x)} + \frac{e^{-x}}{\varphi(x)} \left( \sum_{k=0}^{\ell} (\varphi(k) - \varphi(\ell) + a(\ell-x)) \frac{x^k}{k!} + ax \frac{x^{\ell}}{\ell!} \right), \tag{3.17}
\end{align}$$

and thus we get:

$$\alpha_{\varphi}(x) = \frac{\varphi(\ell) + a(x - \ell)}{\varphi(x)} - \frac{e^{-x}}{\varphi(x)} \left( \sum_{k=0}^{\ell} (\varphi(\ell) + a(x - \ell) - \varphi(k)) \frac{x^k}{k!} - a \frac{x^{\ell+1}}{\ell!} \right).$$
Let us show that it is nondecreasing from $\ell$ to $+\infty$ by computing its derivative. Indeed, for $x \ge \ell$, we have that $\varphi(x) = \varphi(\ell) + a(x - \ell)$ and $\varphi'(x) = a$, so:

$$ \alpha_{\varphi}(x) = 1 - e^{-x} \left( \sum_{k=0}^{\ell} \frac{x^k}{k!} - \frac{1}{\varphi(x)} \left( \sum_{k=0}^{\ell} \varphi(k) \frac{x^k}{k!} + a \frac{x^{\ell+1}}{\ell!} \right) \right). $$

Thus:

$$
\begin{align}
\alpha'_{\varphi}(x) &= e^{-x} \left( \sum_{k=0}^{\ell} \frac{x^k}{k!} - \frac{1}{\varphi(x)} \left( \sum_{k=0}^{\ell} \varphi(k) \frac{x^k}{k!} + a \frac{x^{\ell+1}}{\ell!} \right) \right) \nonumber \\
&\quad - e^{-x} \left( \sum_{k=0}^{\ell-1} \frac{x^k}{k!} - \frac{1}{\varphi(x)} \left( \sum_{k=0}^{\ell-1} \varphi(k+1) \frac{x^k}{k!} + a(\ell+1) \frac{x^{\ell}}{\ell!} \right) \right) \nonumber \\
&\quad + e^{-x} \frac{a}{\varphi(x)^2} \left( \sum_{k=0}^{\ell} \varphi(k) \frac{x^k}{k!} + a \frac{x^{\ell+1}}{\ell!} \right) \nonumber \\
&= e^{-x} \left( \frac{x^{\ell}}{\ell!} - \frac{1}{\varphi(x)} \left( \sum_{k=0}^{\ell-1} (\varphi(k) - \varphi(k+1)) \frac{x^k}{k!} + \varphi(\ell) \frac{x^{\ell}}{\ell!} + (a(x-\ell) - a) \frac{x^{\ell}}{\ell!} \right) \right) \nonumber \\
&\quad - e^{-x} \left( \frac{a}{\varphi(x)^2} \left( \sum_{k=0}^{\ell} \varphi(k) \frac{x^k}{k!} + a \frac{x^{\ell+1}}{\ell!} \right) \right) \nonumber \\
&= e^{-x} \left( \frac{x^{\ell}}{\ell!} + \frac{1}{\varphi(x)} \left( \sum_{k=0}^{\ell-1} (\varphi(k+1) - \varphi(k)) \frac{x^k}{k!} \right) - \frac{\varphi(x) - a}{\varphi(x)} \frac{x^{\ell}}{\ell!} \right) \nonumber \\
&\quad - e^{-x} \frac{a}{\varphi(x)^2} \left( \sum_{k=0}^{\ell} \varphi(k) \frac{x^k}{k!} + a \frac{x^{\ell+1}}{\ell!} \right) \nonumber \\
&= e^{-x} \left( \frac{1}{\varphi(x)} \left( \sum_{k=0}^{\ell-1} (\varphi(k+1) - \varphi(k)) \frac{x^k}{k!} \right) \right) \nonumber \\
&\quad + e^{-x} \frac{a}{\varphi(x)^2} \left( \varphi(x) \frac{x^{\ell}}{\ell!} - \sum_{k=0}^{\ell} \varphi(k) \frac{x^k}{k!} - a \frac{x^{\ell+1}}{\ell!} \right). \tag{3.18}
\end{align}
$$

If $a = 0$, then it is nonnegative since $\varphi$ nondecreasing and nonnegative. Otherwise, suppose that $a > 0$. Then:

$$
\begin{align}
\alpha_{\varphi}(x) &= \frac{ae^{-x}}{\varphi(x)^2} \left( \sum_{k=0}^{\ell-1} \left( \varphi(x) \frac{\varphi(k+1) - \varphi(k)}{a} - \varphi(k) \right) \frac{x^k}{k!} + (\varphi(x) - \varphi(\ell) - ax) \frac{x^\ell}{\ell!} \right) \nonumber \\
&\geq \frac{ae^{-x}}{\varphi(x)^2} \left( \sum_{k=0}^{\ell-1} (\varphi(x) - \varphi(k)) \frac{x^k}{k!} - a \frac{x^\ell}{(\ell-1)!} \right), \tag{3.19}
\end{align}
$$

since $\frac{\varphi(k+1)-\varphi(k)}{a} \geq \frac{\varphi(k+1)-\varphi(k)}{\varphi(\ell)-\varphi(\ell-1)} \geq 1$ by concavity of $\varphi$. Thus:

$$ \alpha_{\varphi}(x) \geq \frac{ae^{-x}}{\varphi(x)^2} \left( \sum_{k=0}^{\ell-1} (\varphi(\ell) - \varphi(k)) \frac{x^k}{k!} + a \left( (x-\ell) \sum_{k=0}^{\ell-1} \frac{x^k}{k!} - \frac{x^\ell}{(\ell-1)!} \right) \right), $$

but:

$$ (x - \ell) \sum_{k=0}^{\ell-1} \frac{x^k}{k!} - \frac{x^\ell}{(\ell-1)!} = \ell \sum_{k=1}^{\ell} \frac{x^k}{k!} - \ell \sum_{k=0}^{\ell-1} \frac{x^k}{k!} - \frac{x^\ell}{(\ell-1)!} = -\ell, $$
so:

$$
\begin{align}
\alpha'_{\varphi}(x) &\ge \frac{ae^{-x}}{\varphi(x)^2} \left( \sum_{k=0}^{\ell-1} (\varphi(\ell) - \varphi(k)) \frac{x^k}{k!} - a\ell \right) \nonumber \\
&\ge \frac{ae^{-x}}{\varphi(x)^2} \left( \sum_{k=0}^{\ell-1} (\varphi(\ell) - \varphi(k)) \frac{x^k}{k!} - (\varphi(\ell) - \varphi(\ell-1))\ell \right) \nonumber \\
&\ge \frac{ae^{-x}}{\varphi(x)^2} \left( \sum_{k=0}^{\ell-1} (\varphi(\ell) - \varphi(k)) \frac{x^k}{k!} - \sum_{k=0}^{\ell-1} (\varphi(\ell) - \varphi(\ell-1)) \frac{x^k}{k!} \right) \tag{3.20} \\
&\text{since } \frac{x^k}{k!} \ge \frac{\ell^k}{k!} \ge 1 \text{ for } k \le \ell \nonumber \\
&= \frac{ae^{-x}}{\varphi(x)^2} \left( \sum_{k=0}^{\ell-1} (\varphi(\ell-1) - \varphi(k)) \frac{x^k}{k!} \right) \ge 0 \quad \text{since } \varphi \text{ nondecreasing.} \nonumber
\end{align}
$$

Thus, $\alpha_{\varphi}(x)$ is nondecreasing from $\ell$ to $+\infty$, and we get that $\alpha_{\varphi} = \min_{x \in [\ell]} \alpha_{\varphi}(x)$. $\square$

**Proposition 3.22.** The Poisson concavity ratio $\alpha_{\varphi}$ is always greater than or equal to the curvature-dependent ratio defined in [SVW17]: if $\varphi$ is linear from $m$ with slope $1-c = \varphi(m) - \varphi(m-1)$, then we have $\alpha_{\varphi} \ge 1 - ce^{-1}$.

*Proof.* Note that by Proposition 3.19, the curvature of $C^{\varphi}$ is equal to $c$, so the efficiency of the algorithm described in [SVW17] is indeed $1 - ce^{-1}$. Thanks to Proposition 3.21, we have that $\alpha_{\varphi} = \min_{x \in [\ell]} \alpha_{\varphi}(x)$, so we only have to show that:

$$
\min_{\ell \in [m]} \alpha_{\varphi}(\ell) \geq 1 - ce^{-1}.
$$

Let us denote by $\varphi^{(\ell,a)}$ the function which is equal to $\varphi$ for $k \le \ell$ and linear from $\ell$ with nonnegative coefficient $a$: $\forall k \ge \ell$, $\varphi^{(\ell,a)}(k) = \varphi(\ell) + a(k - \ell)$. Note that we ask that $0 \le a \le \varphi(\ell) - \varphi(\ell - 1)$ in order to $\varphi^{(\ell,a)}$ to be nondecreasing concave, and $\ell \ge 1$.
This is done in two steps:

1. Let $1 \le \ell \le m$, then:

$$
\alpha_{\varphi}(\ell) = \frac{\mathbb{E}[\varphi(\mathrm{Poi}(\ell))]}{\varphi(\ell)} = \frac{\mathbb{E}[\varphi(\mathrm{Poi}(\ell))]}{\varphi^{(\ell,1-c)}(\ell)} \ge \frac{\mathbb{E}[\varphi^{(\ell,1-c)}(\mathrm{Poi}(\ell))]}{\varphi^{(\ell,1-c)}(\ell)} = \alpha_{\varphi^{(\ell,1-c)}}(\ell),
$$

since $\varphi^{(\ell,1-c)}(x) \le \varphi(x)$ for all $x$. Note that we have:

$$
\varphi(\ell) - \varphi(\ell - 1) \geq \varphi(m) - \varphi(m - 1) = 1 - c,
$$

by concavity of $\varphi$. So, we only have to show that for all $1 \le \ell \le m$, we have
$\alpha^{(\ell,1-c)} := \alpha_{\varphi^{(\ell,1-c)}}(\ell) \ge 1 - ce^{-1}$.

2. Let us show that $\alpha^{(\ell,1-c)} := \alpha_{\varphi^{(\ell,1-c)}}(\ell) \ge 1 - ce^{-1}$ for $1 \le \ell \le m$.
Using the closed-form expression of Proposition 3.21 on $\varphi^{(\ell,1-c)}$ evaluated at $\ell$, one gets:

$$ \alpha^{(\ell,1-c)} = \alpha_{\varphi^{(\ell,1-c)}}(\ell) = 1 - e^{-\ell} \left( \sum_{k=0}^{\ell-1} \left( \frac{\varphi(\ell) - \varphi(k)}{\varphi(\ell)} \right) \frac{\ell^k}{k!} - \frac{1-c}{\varphi(\ell)} \frac{\ell^{\ell+1}}{\ell!} \right). $$

The worst case occurs when $\varphi^{(\ell,1-c)}$ is linear between 1 and $\ell$, which we call $\varphi_{\text{lin}}^{(\ell,1-c)}$. Indeed, with $b := \frac{\varphi(\ell)-1}{\ell-1}$, for $1 \le k \le \ell$, we have that $\varphi_{\text{lin}}^{(\ell,1-c)}(k) = 1 + b(k-1)$. But:

$$ \sum_{k=0}^{\ell-1} \left( \frac{\varphi(\ell) - \varphi(k)}{\varphi(\ell)} \right) \frac{\ell^k}{k!} \le 1 + \sum_{k=1}^{\ell-1} \left( \frac{\varphi(\ell) - (1 + b(k-1))}{\varphi(\ell)} \right) \frac{\ell^k}{k!}, $$

since $\varphi(k) \ge 1 + b(k-1)$, because $\frac{\varphi(k)-\varphi(1)}{k-1} \ge \frac{\varphi(\ell)-\varphi(1)}{\ell-1} = b$ by concavity of $\varphi$. In that case, the expression can be simplified:

$$ \begin{align} \alpha^{(\ell,1-c)} &\ge \alpha_{\varphi_{\text{lin}}^{(\ell,1-c)}}(\ell) = 1 - e^{-\ell} \left( 1 + \sum_{k=1}^{\ell-1} \left( \frac{b(\ell-k)}{\varphi(\ell)} \right) \frac{\ell^k}{k!} - \frac{1-c}{\varphi(\ell)} \frac{\ell^{\ell+1}}{\ell!} \right) \nonumber \\ &= 1 - e^{-\ell} \left( 1 + \frac{b\ell}{\varphi(\ell)} \sum_{k=1}^{\ell-1} \frac{\ell^k}{k!} - \frac{b\ell}{\varphi(\ell)} \sum_{k=1}^{\ell-1} \frac{\ell^{k-1}}{(k-1)!} - \frac{1-c}{\varphi(\ell)} \frac{\ell^{\ell+1}}{\ell!} \right) \nonumber \\ &= 1 - \frac{e^{-\ell}}{\varphi(\ell)} \left( \varphi(\ell) + b\ell \left( \frac{\ell^{\ell-1}}{(\ell-1)!} - 1 \right) - (1-c) \frac{\ell^{\ell+1}}{\ell!} \right) \tag{3.21} \\ &= 1 - \frac{e^{-\ell}}{\varphi(\ell)} \left( 1 + b(\ell-1) + b \left( \frac{\ell^\ell}{(\ell-1)!} - \ell \right) - (1-c) \frac{\ell^{\ell+1}}{\ell!} \right) \nonumber \\ &= 1 - e^{-\ell} \frac{1-b+(b-(1-c))\frac{\ell^{\ell+1}}{\ell!}}{\varphi(\ell)}. \nonumber \end{align} $$

We have also that $b \ge \varphi(\ell) - \varphi(\ell-1) \ge 1-c$ since $\varphi$ concave. As a function of $(b-(1-c))$ for $c$ fixed, we get $g(x) := 1 - e^{-\ell} \frac{c+x(\frac{\ell^{\ell+1}}{\ell!}-1)}{1+(x+(1-c))(\ell-1)}$. In particular, we have that $\alpha_{\varphi_{\text{lin}}^{(\ell,1-c)}}(\ell) = g(b-(1-c))$, since $\varphi(\ell) = 1+b(\ell-1)$. We have that

$g'(x) = -e^{-\ell} \frac{\ell(\frac{\ell^\ell}{\ell!}-1)+(1-c)\frac{\ell^{\ell+1}}{\ell!}(\ell-1)}{(1+(x+(1-c))(\ell-1))^2} \le 0$, so $g$ is nonincreasing: it is thus enough to show that $g(c) \ge 1 - ce^{-1}$ to get the result, since $\alpha^{(\ell,1-c)} \ge g(b-(1-c)) \ge g(c) \ge 1 - ce^{-1}$. But:

$$ g(c) = 1 - \frac{c^{\ell+1}}{1+\ell-1} e^{-\ell} = 1 - c \frac{\ell^\ell}{\ell!} e^{-\ell} \ge 1 - c e^{-1}, $$

since $\frac{\ell^\ell}{\ell!} e^{-\ell}$ is a decreasing sequence.

□

**Proposition 3.23.** Let $F(x) := \mathbb{E}_{X \sim x}[C\varphi(X)]$ for $x \in \{0,1\}^m$. We have an explicit formula for $F$:

$$ F(x) = \sum_{a=1}^{n} \sum_{k=0}^{m} \left[ \frac{1}{m+1} \sum_{\ell=0}^{m} \omega_{m+1}^{-\ell k} \prod_{j \in [m]: a \in T_j} (1 + (\omega_{m+1}^{\ell} - 1)x_j) \right] \varphi(k), $$
with $\omega_{m+1} := \exp(\frac{2i\pi}{m+1})$. Thus, $F$ is computable in polynomial time in $n$ and $m$.

**Proof.** Recall that $C^{\varphi}(S) = \sum_{a=1}^n C_a^{\varphi}(S)$, so by linearity of expectation we focus on $\mathbb{E}_{X \sim x}[C_a^{\varphi}(X)]$. But $C_a^{\varphi}(X) = \varphi(|X|_a)$ where $|X|_a = |\{i \in [m] : X_i = 1 \text{ and } a \in T_i\}|$. Thus:

$$ \mathbb{E}_{X \sim x}[C_a^{\varphi}(X)] = \sum_{k=0}^{m} \mathbb{P}_{X \sim x}(|X|_a = k)\varphi(k). $$

Let us compute the distribution of $|X|_a$. We have $|X|_a = \sum_{i \in [m]: a \in T_i} X_i$ and $X_i \sim \text{Ber}(x_i)$. Thus, $|X|_a \sim \text{Poi Bin}((x_i)_{i \in [m]: a \in T_i})$, which is known as the Poisson binomial law. Thanks to [FW10], we have that:

$$ \mathbb{P}_{X \sim x}(|X|_a = k) = \frac{1}{m+1} \sum_{\ell=0}^{m} \omega_{m+1}^{-\ell k} \prod_{j \in [m]: a \in T_j} (1 + (\omega_{m+1}^{\ell} - 1)x_j), $$

where $\omega_{m+1} := \exp(\frac{2i\pi}{m+1})$, and the result is proved. $\square$

**Proposition 3.24.** We have that

$$ |\mathbb{E}[\varphi(\text{Bin}(n, x/n))] - \mathbb{E}[\varphi(\text{Poi}(x))]| \le \frac{x\varphi(n)}{2n} + \frac{x^{n+1}}{n!}. $$

In particular when $\varphi(n) = o(n)$:

$$ \lim_{n \to \infty} \mathbb{E}[\varphi(\text{Bin}(n, x_{\varphi}/n))] = \mathbb{E}[\varphi(\text{Poi}(x_{\varphi}))] = \alpha_{\varphi}\varphi(x_{\varphi}). $$

**Proof.** Thanks to [BH84, TT19], the total variation distance between $\text{Bin}(n, x/n)$ and $\text{Poi}(x)$ is bounded in the following way:

$$ \Delta(\text{Bin}(n, x/n), \text{Poi}(x)) \le \frac{1 - e^{-x}}{2x} n \cdot \left(\frac{x}{n}\right)^2 \le \frac{x}{2n}. $$

Thus with $B \sim \text{Bin}(n, x/n)$ and $P \sim \text{Poi}(x)$:

$$
\begin{align*}
|\mathbb{E}[\varphi(B)] - \mathbb{E}[\varphi(P)]| &= \left| \sum_{k=0}^{+\infty} \varphi(k) \mathbb{P}(B=k) - \sum_{k=0}^{+\infty} \varphi(k) \mathbb{P}(P=k) \right| \\
&= \left| \sum_{k=0}^{+\infty} \varphi(k) (\mathbb{P}(B=k) - \mathbb{P}(P=k)) \right| \\
&\le \sum_{k=0}^{+\infty} \varphi(k) |\mathbb{P}(B=k) - \mathbb{P}(P=k)| \\
&\le \varphi(n) \Delta(\text{Bin}(n, x/n), \text{Poi}(x)) + \sum_{k=n+1}^{+\infty} \varphi(k) \mathbb{P}(P=k) \tag{3.22} \\
&\le \frac{x\varphi(n)}{2n} + e^{-x} \sum_{k=n+1}^{+\infty} k \frac{x^k}{k!} \quad \text{since } \varphi(k) \le k \\
&= \frac{x\varphi(n)}{2n} + xe^{-x} \sum_{k=n}^{+\infty} \frac{x^k}{k!} \\
&\le \frac{x\varphi(n)}{2n} + \frac{x^{n+1}}{n!} \quad \underset{n \to \infty}{\to} 0 \quad \text{when } \varphi(n) = o(n),
\end{align*}
$$
by a standard upper bound on the remainder of the exponential series.

□

**Proposition 3.25.** The function $g: x \mapsto \mathbb{E}[\varphi(\mathrm{Poi}(x))]$ on $\mathbb{R}^+$ is $C^\infty$ nondecreasing concave.

*Proof.* Since we have that $0 \le \varphi(k) \le k$ for $k \in \mathbb{N}$, in particular $g(x) = e^{-x} \sum_{k=0}^{+\infty} \varphi(k) \frac{x^k}{k!}$ is $C^\infty$. It is thus enough to compute its first and second derivatives:

$$ 
\begin{aligned}
g'(x) &= -e^{-x} \sum_{k=0}^{+\infty} \varphi(k) \frac{x^k}{k!} + e^{-x} \sum_{k=1}^{+\infty} \varphi(k) k \frac{x^{k-1}}{k!} \\
&= -e^{-x} \sum_{k=0}^{+\infty} \varphi(k) \frac{x^k}{k!} + e^{-x} \sum_{k=0}^{+\infty} \varphi(k+1) \frac{x^k}{k!} \quad (3.23) \\
&= e^{-x} \sum_{k=0}^{+\infty} (\varphi(k+1) - \varphi(k)) \frac{x^k}{k!}.
\end{aligned}
$$

But $\varphi(k+1) - \varphi(k) \ge 0$ since $\varphi$ nondecreasing, so $g'(x) \ge 0$ and $g$ is nondecreasing.

The calculus of $g''$ is the same where we replace $\varphi$ by $\psi(k) := \varphi(k+1) - \varphi(k)$ which is a nonincreasing function by concavity of $\varphi$. Thus:

$$ g''(x) = e^{-x} \sum_{k=0}^{+\infty} (\psi(k+1) - \psi(k)) \frac{x^k}{k!} \le 0. $$

since $\psi(k+1) - \psi(k) \le 0$, and so $g$ is concave.

□

**Proposition 3.26.** The function $g_q: n \mapsto \mathbb{E}[\varphi(\mathrm{Bin}(n, q))]$ defined on $\mathbb{N}$ is nondecreasing concave. As a consequence, one can use Jensen's inequality on the piecewise linear extension of $g_q$ which is also continuous.

*Proof.* We have $\mathrm{Bin}(n, q) \le \mathrm{Bin}(n+1, q)$ and $\mathbb{E}[\varphi(\mathrm{Bin}(n, q))] \le \mathbb{E}[\varphi(\mathrm{Bin}(n+1, q))]$ since $\varphi$ is nondecreasing, ie $g_q(n+1) - g_q(n) \ge 0$: $g_q$ is nondecreasing.

We show then the concavity, i.e. $g_q(n+2) - g_q(n+1) \le g_q(n+1) - g_q(n)$. Let us define $\psi(x) = \varphi(x+1) - \varphi(x)$, which is nonincreasing since $\varphi$ concave. Let us take $X_{k,q} \sim \mathrm{Bin}(k, q)$. Then:

$$ 
\begin{aligned}
g_q(n+1) &= \mathbb{E}[\varphi(X_{n+1,q})] \\
&= \sum_{i=0}^{n} \mathbb{E}[\varphi(X_{n,q} + X_{1,q}) | X_{n,q} = i] \mathbb{P}(X_{n,q} = i) \\
&= \sum_{i=0}^{n} \mathbb{E}[\varphi(i + X_{1,q}) - \varphi(i)] \mathbb{P}(X_{n,q} = i) + \sum_{i=0}^{n} \varphi(i) \mathbb{P}(X_{n,q} = i) \quad (3.24) \\
&= \sum_{i=0}^{n} \mathbb{E}[\varphi(i + X_{1,q}) - \varphi(i)] \mathbb{P}(X_{n,q} = i) + g_q(n).
\end{aligned}
$$
Thus:

$$
\begin{align}
g_q(n+1) - g_q(n) &= \sum_{i=0}^{n} \mathbb{E}[\varphi(i+X_{1,q}) - \varphi(i)] \mathbb{P}(X_{n,q} = i) \nonumber \\
&= \sum_{i=0}^{n} q(\varphi(i+1) - \varphi(i)) \mathbb{P}(X_{n,q} = i) \tag{3.25} \\
&= q \mathbb{E}[\psi(\text{Bin}(n, q))] . \nonumber
\end{align}
$$

Then thanks to the fact that $\text{Bin}(n, q) \le_{\text{st}} \text{Bin}(n+1, q)$ and $\psi$ is nonincreasing, we have that
$\mathbb{E}[\psi(\text{Bin}(n, q))] \ge \mathbb{E}[\psi(\text{Bin}(n+1, q))]$, i.e. $g_q(n+2) - g_q(n+1) \le g_q(n+1) - g_q(n)$. $\square$

**Proposition 3.27.** With $w_i := \varphi(i) - \varphi(i-1)$, we have:

$$
\lim_{i \to +\infty} w_i = 0 \iff \varphi(n) = o(n).
$$

*Proof.* (⇒) Let $\epsilon > 0$, let us find a rank $N$ such that for $n \ge N$, $\frac{\varphi(n)}{n} \le \epsilon$. Let $N_0$ the rank from which $w_i \le \frac{\epsilon}{2}$ and $N_1$ the rank from which $\frac{1}{n} \sum_{i=1}^{N_0-1} w_i \le \frac{\epsilon}{2}$. We have

$$
\begin{align}
\frac{\varphi(n)}{n} &= \frac{1}{n} \sum_{i=1}^{n} w_i \le \frac{1}{n} \sum_{i=1}^{N_0-1} w_i + \frac{1}{n} \sum_{i=N_0}^{n-1} \frac{\epsilon}{2} \tag{3.26} \\
&\le \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon \text{ for } n \ge \max(N_0, N_1) =: N. \notag
\end{align}
$$

(⇔) Since $w_i = \varphi(i) - \varphi(i-1)$ is nonnegative and nonincreasing (respectively because
$\varphi$ is nondecreasing and concave), then the sequence $w$ has a limit $L \ge 0$. But

$$
\frac{\varphi(n)}{n} = \frac{1}{n} \sum_{i=1}^{n} w_i \geq L.
$$

Since the left hand side tends to 0 by hypothesis, this means that $L = 0$.

<figure><img src="image_8.png" /></figure>

**Proposition 3.28.** If $w_i := \varphi(i) - \varphi(i-1)$ is geometrically dominant, i.e. it satisfies
$\forall i \in \mathbb{N}^*, \frac{w_i}{w_{i+1}} \ge \frac{w_{i+1}}{w_{i+2}}$, then $\alpha_\varphi = \alpha_\varphi(1)$.

*Remark.* Proposition 3.28 and in particular its proof uses similar ideas to the sketch provided in [DMMS20].

*Proof.* Let $g(k) := \mathbb{E}[\varphi(\text{Poi}(k))]$, and thus $\alpha_{\varphi}(k) = \frac{g(k)}{\varphi(k)}$. Let us show that for $k \in \mathbb{N}^*$, $\alpha_{\varphi}(k) \ge \alpha_{\varphi}(1)$, which will be enough to conclude. In order to show this, we will need the following lemmas:

**Lemma 3.29.** $\forall k < i \in \mathbb{N}, w_i \ge w_{k+1}w_{i-k}$ and thus $\forall k, j \in \mathbb{N}, \varphi(k+j) - \varphi(k) \ge w_{k+1}\varphi(j)$.
Proof. We have that:

$$w_i = \frac{w_i}{w_{i-1}} \frac{w_{i-1}}{w_{i-2}} \cdots \frac{w_{i-k+1}}{w_{i-k}} w_{i-k}.$$

But for $j \in [k]$:

$$\frac{w_{i-j+1}}{w_{i-j}} \ge \frac{w_{(i-1)-j+1}}{w_{(i-1)-j}} \ge \dots \ge \frac{w_{(k+1)-j+1}}{w_{(k+1)-j}},$$

since $w$ is geometrically dominant and $k+1 \le i$. Thus applying this bound on each term of the previous product, we get:

$$w_i \ge \frac{w_{k+1}}{w_k} \frac{w_k}{w_{k-1}} \cdots \frac{w_2}{w_1} w_{i-k} = \frac{w_{k+1}}{w_1} w_{i-k} = w_{k+1} w_{i-k}.$$

In particular, $\forall k, j \in \mathbb{N}$, we get:

$$\varphi(k+j) - \varphi(k) = \sum_{i=k+1}^{k+j} w_i \ge w_{k+1} \sum_{i=1}^{j} w_i = w_{k+1} \varphi(j).$$

□

**Lemma 3.30.** The piecewise linear extension on $[1, +\infty[$ of $w$, defined on integers with $w(k) := w_k$, is convex.

Proof. We will show that $\forall k \in \mathbb{N}^*$, $w_{k+2} - w_{k+1} \ge w_{k+1} - w_k$ which implies the convexity of its piecewise linear extension on $[1, +\infty[$. For $k \in \mathbb{N}^*$ we have:

$$\frac{w_{k+1}}{w_{k+2}} - 1 \le \frac{w_{k+1}}{w_{k+2}} \left( \frac{w_{k+1}}{w_{k+2}} - 1 \right) \le \frac{w_{k+1}}{w_{k+2}} \left( \frac{w_k}{w_{k+1}} - 1 \right) = \frac{w_k - w_{k+1}}{w_{k+2}},$$

since $w$ is nonnegative nonincreasing (respectively $\varphi$ nondecreasing concave) and $\frac{w_{k+1}}{w_{k+2}} \le \frac{w_k}{w_{k+1}}$ since $w$ is geometrically dominant. Then, multiplying by $-w_{k+2} \le 0$ gives the expected result $w_{k+2} - w_{k+1} \ge w_{k+1} - w_k$. □

We have $g(k+1) = \mathbb{E}[\varphi(\text{Poi}(k+1))] = \mathbb{E}[\varphi(\text{Poi}(k) + \text{Poi}(1))]$ since $\text{Poi}(k+1) \sim \text{Poi}(k) + \text{Poi}(1)$. Thus:

$$\begin{align}
g(k+1) - g(k) &= \mathbb{E}_{X,X' \sim \text{Poi}(k), Y \sim \text{Poi}(1)}[\varphi(X+Y) - \varphi(X')] \nonumber \\
&= \mathbb{E}_{X \sim \text{Poi}(k), Y \sim \text{Poi}(1)}[\varphi(X+Y) - \varphi(X)] \tag{3.27} \\
&\ge \mathbb{E}_{X \sim \text{Poi}(k), Y \sim \text{Poi}(1)}[w_{X+1}\varphi(Y)] \quad \text{by Lemma 3.29} \nonumber \\
&= \mathbb{E}_{X \sim \text{Poi}(k)}[w(X+1)]\mathbb{E}_{Y \sim \text{Poi}(1)}[\varphi(Y)], \nonumber
\end{align}$$

by independence of $w(X+1)$ and $\varphi(Y)$. Since $w$ is convex on $[1, +\infty[$ by Lemma 3.30 and $\text{Poi}(k)+1 \in [1, +\infty[$, we have that $\mathbb{E}[w(\text{Poi}(k)+1)] \ge w(\mathbb{E}[\text{Poi}(k)+1]) = w(k+1) = w_{k+1}$ thanks to Jensen's inequality. Note that $g(0) = \mathbb{E}[\varphi(\text{Poi}(0))] = \varphi(0) = 0$. Then:

$$g(k) = \sum_{i=0}^{k-1} g(i+1) - g(i) \ge \left( \sum_{i=0}^{k-1} w_{i+1} \right) \mathbb{E}[\varphi(\text{Poi}(1))] = \varphi(k)g(1).$$

Therefore:

$$\alpha_{\varphi}(k) = \frac{g(k)}{\varphi(k)} \ge g(1) = \frac{g(1)}{\varphi(1)} = \alpha_{\varphi}(1).$$

□
### 3.5.2 Calculations of $\alpha_{\varphi}$

**Proposition 3.31.** For $\ell \in \mathbb{N}^*$ and $\varphi(j) = \min(j, \ell)$, we have that $\alpha_{\varphi} = 1 - \frac{\ell^\ell e^{-\ell}}{\ell!}$.

*Proof.* Thanks to Proposition 3.22, we have that $\alpha_{\varphi} = \min_{x \in \mathbb{N}^*} \alpha_{\varphi}(x)$. Let us compute $\mathbb{E}[\varphi(\text{Poi}(x))]$:

$$ 
\begin{aligned}
\mathbb{E}[\varphi(\text{Poi}(x))] &= e^{-x} \sum_{k=0}^{+\infty} \varphi(k) \frac{x^k}{k!} \\
&= e^{-x} \sum_{k=0}^{\ell} k \frac{x^k}{k!} + e^{-x} \sum_{k=\ell+1}^{+\infty} \ell \frac{x^k}{k!} \\
&= e^{-x} x \sum_{k=0}^{\ell-1} \frac{x^k}{k!} + \ell e^{-x} \sum_{k=\ell+1}^{+\infty} \frac{x^k}{k!} \quad (3.28) \\
&= e^{-x} \left[ (x-\ell) \sum_{k=0}^{\ell-1} \frac{x^k}{k!} - \ell \frac{x^\ell}{\ell!} \right] + \ell e^{-x} \sum_{k=0}^{+\infty} \frac{x^k}{k!} \\
&= \ell - e^{-x} \left[ \frac{x^\ell}{(\ell-1)!} - (x-\ell) \sum_{k=0}^{\ell-1} \frac{x^k}{k!} \right].
\end{aligned}
$$

Let us show that $x \mapsto \alpha_{\varphi}(x)$ takes its minimum in $\ell$, where we have indeed:

$$ \alpha_{\varphi}(\ell) = \frac{1}{\ell} \left( \ell - e^{-\ell} \left[ \frac{\ell^{\ell}}{(\ell-1)!} - (\ell-\ell) \sum_{k=0}^{\ell-1} \frac{\ell^k}{k!} \right] \right) = 1 - e^{-\ell} \frac{\ell^{\ell}}{\ell!}. $$

Thanks to proposition 3.21, $x \mapsto \alpha_{\varphi}(x)$ is nondecreasing from $\ell$ to $+\infty$. Suppose now that $\ell \ge 2$ (otherwise the result is already proved). Since $x \mapsto \alpha_{\varphi}(x)$ is differentiable, we have
for $1 \le x \le \ell$:

$$
\begin{align*}
\alpha'_{\varphi}(x) &= -\frac{\ell}{x^2} + e^{-x} \left[ \frac{x^{\ell-1}}{(\ell-1)!} - \sum_{k=0}^{\ell-1} \frac{x^k}{k!} + \ell \sum_{k=0}^{\ell-2} \frac{x^k}{(k+1)!} + \frac{\ell}{x} \right] \\
&\quad - e^{-x} \left[ \frac{x^{\ell-2}}{(\ell-2)!} - \sum_{k=0}^{\ell-2} \frac{x^k}{k!} + \ell \sum_{k=0}^{\ell-3} \frac{x^k}{(k+2)k!} - \frac{\ell}{x^2} \right] \\
&= \frac{\ell}{x} \left( e^{-x} \left( 1 + \frac{1}{x} \right) - \frac{1}{x} \right) \\
&\quad + e^{-x} \left[ \left( \frac{\ell}{\ell-1} - 1 \right) \frac{x^{\ell-2}}{(\ell-2)!} + \ell \sum_{k=0}^{\ell-3} \left( \frac{x^k}{(k+1)!} - \frac{x^k}{(k+2)k!} \right) \right] \\
&= \frac{\ell}{x} \left( e^{-x} \left( 1 + \frac{1}{x} \right) - \frac{1}{x} \right) + e^{-x} \left[ \frac{x^{\ell-2}}{(\ell-1)!} + \ell \sum_{k=0}^{\ell-3} \frac{x^k}{k!} \left( \frac{1}{k+1} - \frac{1}{k+2} \right) \right] \\
&= \frac{\ell}{x} \left( e^{-x} \left( 1 + \frac{1}{x} + \frac{x^{\ell-1}}{\ell!} + x \sum_{k=0}^{\ell-3} \frac{x^k}{k!} \frac{1}{(k+1)(k+2)} \right) - \frac{1}{x} \right) \\
&= \frac{\ell e^{-x}}{x^2} \left( \left( 1 + x + \frac{x^{\ell}}{\ell!} + \sum_{k=0}^{\ell-3} \frac{x^{k+2}}{(k+2)!} \right) - e^x \right) \\
&= \frac{\ell e^{-x}}{x^2} \left( \sum_{k=0}^{\ell} \frac{x^k}{k!} - e^x \right) \le 0. \tag{3.29}
\end{align*}
$$

since the partial sum of the exponential series is bounded by its total sum. Thus $\alpha_{\varphi}(x)$ is nonincreasing from 1 to $\ell$, and nondecreasing after, so it takes indeed its minimum in $\ell$ and the proposition is proved. $\square$

**Proposition 3.32.** For $p \in (0, 1)$ and $\varphi(j) = \frac{1-(1-p)^j}{p}$, we have that $\alpha_{\varphi} = \frac{1-e^{-p}}{p}$.

*Proof.* By definition:

$$
\begin{align}
\alpha_{\varphi}(x) &= \frac{\mathbb{E}[\varphi(\mathrm{Poi}(x))]}{\varphi(x)} = \frac{\sum_{k=0}^{+\infty} \varphi(k) e^{-x} \frac{x^k}{k!}}{\varphi(x)} \nonumber \\
&= \frac{1 - e^{-x} \sum_{k=0}^{+\infty} (1-p)^k \frac{x^k}{k!}}{p\varphi(x)} \tag{3.30} \\
&= \frac{1 - e^{-x} e^{(1-p)x}}{p\varphi(x)} = \frac{1 - e^{-px}}{p\varphi(x)}. \nonumber
\end{align}
$$

If $x \ge 1$, $\alpha_{\varphi}(x) = \frac{1-e^{-px}}{1-(1-p)^x} = \frac{1-e^{-px}}{1-e^{-qx}}$ with $q = \ln(\frac{1}{1-p}) > 0$ and:

$$
\alpha'_{\varphi}(x) = \frac{pe^{-px}(1 - e^{-qx}) - qe^{-qx}(1 - e^{-px})}{(1 - e^{-qx})^2} = \frac{pe^{-px} - qe^{-qx} + (q-p)e^{-(p+q)x}}{(1 - e^{-qx})^2}.
$$

Let us take $t = \frac{p}{q} \in (0, 1)$, since $q = \ln(\frac{1}{1-p}) > p > 0$, $x_1 = -px$ and $x_2 = -(p+q)x$.
Then by strict convexity of the exponential function, we have:

$$
e^{tx_1+(1-t)x_2} < t e^{x_1} + (1-t)e^{x_2} = \frac{pe^{-px} + (q-p)e^{-(p+q)x}}{q}.
$$
But $tx_1 + (1-t)x_2 = \frac{-p^2x}{q} + \frac{-(q-p)(p+q)x}{q} = \frac{-p^2x}{q} + \frac{-(q^2x-p^2x)}{q} = -qx$, so we get $pe^{-px} - qe^{-qx} + (q-p)e^{-(p+q)x} > 0$, and $\alpha'_{\varphi}(x) > 0$. Thus, $\alpha_{\varphi}(x)$ increases from 1 to infinity and takes its minimum in 1:

$$ \alpha_{\varphi} = \alpha_{\varphi}(1) = \frac{1 - e^{-p}}{p}. $$

<figure><img src="image_9.png" /></figure>

**Proposition 3.33.** For $d \in (0, 1)$ and $\varphi(j) = j^d$, we have that $\alpha_{\varphi} = e^{-1} \sum_{k=1}^{+\infty} \frac{k^d}{k!}$.

*Proof.* We have for $x \ge 1$:

$$ \alpha_{\varphi}(x) = \frac{\mathbb{E}[\text{Poi}(x)^d]}{\varphi(x)} = \frac{e^{-x} \sum_{k=0}^{+\infty} k^d \frac{x^k}{k!}}{\varphi(x)} = e^{-x} \sum_{k=0}^{+\infty} k^d \frac{x^{k-d}}{k!}. $$

Then:

$$ \begin{aligned} \alpha'_{\varphi}(x) &= -\alpha_{\varphi}(x) + e^{-x} \sum_{k=1}^{+\infty} (k-d)k^d \frac{x^{k-d-1}}{k!} \\ &= -\alpha_{\varphi}(x) + e^{-x} \sum_{k=0}^{+\infty} (k+1-d)(k+1)^d \frac{x^{k-d}}{(k+1)!} \\ &= -\alpha_{\varphi}(x) + e^{-x} \left( (1-d)x^{-d} + \sum_{k=1}^{+\infty} (k+1-d)(k+1)^{d-1} \frac{x^{k-d}}{k!} \right) \quad (3.31) \\ &= e^{-x}x^{-d} \left( 1 - d + \sum_{k=1}^{+\infty} \left( \frac{k+1-d}{k+1}(k+1)^d - k^d \right) \frac{x^k}{k!} \right). \end{aligned} $$

But the function $f(k) = \frac{k+1-d}{k+1}(k+1)^d - k^d$ is positive on $\mathbb{R}_+^*$, so we get that $\alpha'_{\varphi}(x) > 0$ for $x \ge 1$, thus $\alpha_{\varphi}(x)$ is increasing from 1 to $+\infty$, so $\alpha_{\varphi} = \alpha_{\varphi}(1) = e^{-1} \sum_{k=1}^{+\infty} \frac{k^d}{k!}$. $\square$

### 3.5.3 NP-hardness of $\delta$, h-ARYGAPLABELCOVER

*Proof of Proposition 3.5.* We reduce from the Label Cover problem described in [DMMS20] which is known to be an NP-hard problem. The main idea of this reduction is the usual equivalence between bipartite graphs and hypergraphs.

**Definition 3.5.** A Label Cover instance $\mathcal{L} = (A \sqcup B, E, [L], [R], \{\pi_e\}_{e \in E})$ consists of a bi-regular bipartite graph $(A \sqcup B, E)$ with right degree $t$, alphabet sets $[L]$, $[R]$ and for every edge $e \in E$, a constraint $\pi_e : [L] \to [R]$. A labeling of $\mathcal{L}$ is a function $\sigma : A \to [L]$. We say that $\sigma$ strongly satisfies a right vertex $v \in B$ if for every two neighbors $u, u'$ of $v$, we have $\pi_{(u,v)}(\sigma(u)) = \pi_{(u',v)}(\sigma(u'))$. Moreover, we say that $\sigma$ weakly satisfies a right vertex $v \in B$ if there exists two neighbors $u, u'$ of $v$ such that $\pi_{(u,v)}(\sigma(u)) = \pi_{(u',v)}(\sigma(u'))$.

**Theorem 3.34** ($\delta$-Gap-Label-Cover($t, R$) from [DMMS20]). For any fixed integer $t \ge 2$ and fixed $\delta > 0$, there exists $R_0$ such that for any integer $R \ge R_0$, it is NP-hard for Label Cover instances $\mathcal{L} = (A \sqcup B, E, [L], [R], \{\pi_e\}_{e \in E})$ with right degree $t$ and right alphabet $[R]$ to distinguish between:
**YES:** There exists a labeling $\sigma$ that strongly satisfies all the right vertices.

**NO:** No labeling weakly satisfies more than $\delta$ fraction of the right vertices.

The reduction is the following. From $\delta$-Gap-Label-Cover($t, R$), we take $h = t$ and the same parameters $\delta, R$. Given an instance $\mathcal{L} = (A \sqcup B, E, [L], [R], \{\pi_e\}_{e \in E})$, we take $\mathcal{G} = (A, E', [L], [R], \{\pi'_{e',v}\}_{e' \in E', v \in e'})$ with $E' = \{N(b), b \in B\}$ with $N(b)$ the set of neighbors of $b$ in $\mathcal{L}$, and $\pi'_{e',v} = \pi'_{N(b),v} := \pi_{v,b}$ since $v \in N(b)$. Since $(A \sqcup B, E)$ is bipartite and biregular, we get that our hypergraph has all hyperedges of size $h = |N(b)| = t$, and that it is regular from the regular left degree of $(A \sqcup B, E)$. By construction, the notion of weakly and strongly satisfied is the same in both cases, as well as the labelings, and thus we have the NP-hardness of $\delta$, h-ARYGAPLABELCOVER.

Note that both problems are in fact linearly equivalent since we could do the same reduction backwards.

<figure><img src="image_10.png" /></figure>

### 3.5.4 Proof of Existence of Partitioning Systems

*Proof of Proposition 3.6.* The existential proof is based on the probabilistic method. We take $P_i$ an $h$-equi-sized uniform random $x_\varphi$-cover of $[n]$. Hence in the collection $P_i = (P_{i,1}, \dots, P_{i,h})$, each of the $h$ subsets is of cardinality $\frac{x_\varphi n}{h}$. Write $\mathcal{P} = (\mathcal{P}_1, \dots, \mathcal{P}_R)$. We have that for any $a \in [n]$, $\mathbb{P}(a \in P_{i,j}) = \frac{x_\varphi}{h}$. Note that these events are independent for different $i$s.

By construction, the first condition is fulfilled. Let us prove the second one.

Fix $T \subseteq [R]$ and $\mathcal{Q} := \{P_{i,j(i)} : i \in T\}$ for some function $j : T \to [h]$. We have for $a \in [n]$:

$$ \mathbb{E}[C_a^\varphi(\mathcal{Q})] = \mathbb{E}[\varphi(|\mathcal{Q}|_a)] = \mathbb{E}\left[\varphi\left(|\{i \in T : a \in P_{i,j(i)}\}|\right)\right]. $$

But the random variables $\{X_i^a := 1_{a \in P_{i,j(i)}}\}_{i \in T}$ are independent and $X_i^a \sim \text{Ber}(\frac{x_\varphi}{h})$, so $X^a := |\{i \in T : a \in P_{i,j(i)}\}| = \sum_{i \in T} X_i^a \sim \text{Bin}(|T|, \frac{x_\varphi}{h})$, and thus:

$$ \mathbb{E}[C_a^\varphi(\mathcal{Q})] = \mathbb{E}\left[\varphi\left(\text{Bin}\left(|T|, \frac{x_\varphi}{h}\right)\right)\right] = \psi_{|T|,h}^\varphi. $$

Since $|\mathcal{Q}|_a \le |\mathcal{Q}| \le R$ and $\varphi$ nondecreasing, we have $0 \le C_a^\varphi(\mathcal{Q}) \le \varphi(R)$. The random variables $\{C_a^\varphi(\mathcal{Q})\}_{a \in [n]}$ are not independent in general. However, we will show that they are negatively associated (see Definition 2.2), thus we can apply the version of the Chernoff-Hoeffding bound described in Proposition 2.9 to get:

$$ \mathbb{P}\left(\left|\frac{1}{n}\sum_{a \in [n]} C_a^\varphi(\mathcal{Q}) - \psi_{|T|,h}^\varphi\right| > \eta\right) \le 2 \exp\left(-2\left(\frac{\eta}{\varphi(R)}\right)^2 n\right). $$

Note that $C_a^\varphi(\mathcal{Q}) = \varphi(|\mathcal{Q}|_a) = \varphi(X^a)$ is a nondecreasing function of $\{X_i^a\}_{i \in [R]}$, since $\varphi$ is nondecreasing and $X^a = \sum_{i \in T} X_i^a$. Thus in order to show that $\{C_a^\varphi(\mathcal{Q})\}_{a \in [n]}$ are negatively associated, it suffices to show that $\{X_i^a\}_{i \in [R], a \in [n]}$ are negatively associated by Proposition 2.6.
For fixed $i \in [R]$, $\{X_i^a\}_{a \in [n]}$ are negatively associated because it corresponds to a permutation distribution of $(0, \dots, 0, 1, \dots, 1)$, with $n - \frac{x_\varphi n}{h}$ zeros and $\frac{x_\varphi n}{h}$ ones, since it describes a random subset of size $\frac{x_\varphi n}{h}$; see Definition 2.3 and Proposition 2.8. Then, using the fact that the families $\{X_i^a\}_{a \in [n]}$ are mutually independent, we obtain that $\{X_i^a\}_{i \in [R], a \in [n]}$ are negatively associated by Proposition 2.7.

Since there are at most $(h+1)^R$ choices of $T$ and $Q$, a union bound gives:

$$ \mathbb{P}(\exists C, Q: |C^\varphi(Q) - \psi_{[T],h}^\varphi n| > \eta n) \le 2(h+1)^R \exp\left(-2\left(\frac{\eta}{\varphi(R)}\right)^2 n\right). $$

Thus with probability at least 9/10, we have that $|C^\varphi(Q) - \psi_{[T],h}^\varphi n| \le \eta n$, since we have taken $n \ge \eta^{-2}R\varphi(R)^2 \log(20(h+1))$. So there must exists some choice of $\mathcal{P}$ that satisfies the first and second constraints of partitioning systems. Thus, we can enumerate over all choices of $\mathcal{P}$ in time $\exp(Rn \log(n)) \cdot \text{poly}(h)$ to find such a partitioning system. $\square$

### 3.5.5 Proof of Theorem 3.15

*Proof.* We show that $\varphi$-RESOURCE ALLOCATION corresponds to $\varphi$-MAXCOVERAGE under a matroid constraint. Given an instance of $\varphi$-RESOURCE ALLOCATION, consider the partition matroid $\mathcal{M}$ on $[\sum_{i \in [k]} m_i] := [m_1] + \dots + [m_k]$, where $(B_i)_{i \in [k]} := ([m_i])_{i \in [k]}$ is a partition of the ground set and the cardinality constraint for each $i$ is to $d_i = 1$.

Here, $I \subseteq [\sum_{i \in [k]} m_i]$ is an independent set of the matroid if and only if $|I \cap B_i| \le d_i = 1$, for all $i \in [k]$. This corresponds to each agent $i \in [k]$ selecting at most one element from the available $m_i$ choices. In other words, we have a bijection $f$ between tuples $(A_1, \dots, A_k) \in \mathcal{A}_1 \times \dots \times \mathcal{A}_k$ and maximal independent sets (bases) of $\mathcal{M}$ such that $W^\varphi(A) = C^\varphi(f(A))$. Therefore, Theorem 3.3 leads to a polynomial-time $\alpha_\varphi$-approximation algorithm for $\varphi$-RESOURCE ALLOCATION.

For the hardness part of the theorem, the proof is exactly the same as in Theorem 3.4, but instead of $\mathcal{F} := \{F_\beta^v, v \in V, \beta \in [L]\}$ and $k = |V|$, we take $k = |V|$ to be the number of agents and $\mathcal{A}_i := \{F_\beta^{v_i}, \beta \in [L]\}$ where $V = \{v_1, \dots, v_k\}$. Hence, instead of subsets of $\mathcal{F}$ of size $k$, we only consider one set $F_\beta^v \in \mathcal{F}$, for each $v \in V$. The function we maximize in the reduction remains unchanged.

To establish completeness, we note that the subset described is already of the right form and, hence, the arguments continue to hold. For proving soundness, the constraint on the shape of the subset of $\mathcal{F}$ only helps us, since it gives more constraints on the given subset from which we want to construct a labeling. Therefore, the NP-hardness follows. $\square$
<figure><img src="image_11.png" /></figure>
Multiple-Access Channel Coding
With Non-Signaling Correlations

Multiple-access channels (MACs for short) are one of the simplest models of network communication settings, where two senders aim to transmit individual messages to one receiver. The capacity of such channels has been entirely characterized by the seminal works by Liao [Lia73] and Ahlswede [Ahl73] in terms of a simple single-letter formula. From the point of view of quantum information, it is natural to ask whether additional resources, such as quantum entanglement or more generally non-signaling correlations between the parties, change the capacity region. A non-signaling correlation is a multipartite input-output box shared between parties that, as the name suggests, cannot by itself be used to send information between parties. However, non-signaling correlations such as the ones generated by measurements of entangled quantum particles, can provide an advantage for various information processing tasks and nonlocal games. The study of such correlations has given rise to the quantum information area known as nonlocality [BCP<sup>+</sup>14]. For example, in the context of channel coding, there exists classical point-to-point channels for which quantum entanglement between the sender and the receiver can increase the optimal success probability for sending one bit of information with a single use of the channel [PLM<sup>+</sup>11, BF18]. However, for classical point-to-point channels, entanglement [BBC<sup>+</sup>93, BSST99] and even more generally non-signaling correlations [Mat12] do not change the capacity of the channel.

In the network setting, behavior is different. Quek and Shor showed in [QS17] the existence of two-sender two-receiver interference channels with gaps between their classical, quantum-entanglement assisted and non-signaling assisted capacity regions. Following this result, Leditzky et al. [LALS20, SLSS22] showed that quantum entanglement shared between the two senders of a MAC can strictly enlarge the capacity region. This has been demonstrated through channels that are constructed from two-player nonlocal games, such as the Magic Square game [Mer90, Per90, Ara02, BBT05], by translating known gaps between classical and quantum values of games into MAC capacity gaps. Other instances of network channels for which entanglement increases the capacity region were studied in [Noe20, ND20, YRB20, YRB23]. This raises the following natural question: Can non-signaling correlations lead to significant gains in capacity for natural MACs? Can we find a characterization of the capacity region of the MAC when non-signaling resources between the parties are allowed?
**Contributions** We focus here on the MAC with two senders and we allow arbitrary tripartite non-signaling correlations between the two senders and the receiver. This is the most optimistic setting, in the sense that we only enforce the non-signaling constraints between the parties, and also the mathematically simplest setting. Even if not all non-signaling correlations are feasible within quantum theory, the setting we study here can be seen as a tractable and physically motivated outer approximation of what can be achieved with quantum theory. In fact, the quantum set is notoriously complicated and deciding membership in this set is not computable [JNV+20]. We note that very recently, Pereg et al. [PDB23] found a regularized characterization for the capacity of MACs with quantum entanglement shared between the two senders. Unfortunately, even the associated single-letter inner bound is very difficult to evaluate for any fixed channel.

We first show that the multiple-access channel coding problem, which entails maximizing the success probability of sending a fixed number of messages through a MAC, cannot be approximated in polynomial time within any constant ratio, under a complexity hypothesis on random $k$-SAT formulas; see Theorem 4.5.

We denote by $S^{\text{NS}}(W, k_1, k_2)$ the success probability of the best non-signaling assisted $(k_1, k_2)$-code for the MAC $W$. Contrary to the unassisted value that we denote $S(W, k_1, k_2)$, $S^{\text{NS}}(W, k_1, k_2)$ can be formulated as a linear program; see Proposition 4.7. Furthermore, using symmetries, we have developed a linear program computing $S^{\text{NS}}$ for a finite number of copies of a MAC $W$ with a size growing polynomially in the number of copies; see Theorem 4.12 and Corollary 4.13. Using this result, we describe a method to derive inner bounds on the non-signaling assisted capacity region achievable with zero error; see Proposition 4.17. Applied to the binary adder channel, which maps $(x_1, x_2) \in \{0, 1\}^2$ to $x_1 + x_2 \in \{0, 1, 2\}$, we show that the sum-rate $\frac{\log_2(72)}{4} \approx 1.5425$ can be reached with zero error, which beats the maximum classical sum-rate capacity of $\frac{3}{2}$; see Theorem 4.18. For noisy channels, where the zero-error non-signaling assisted capacity region is trivial, we can use concatenated codes to obtain achievable points in the capacity region; see Proposition 4.20. Applied to a noisy version of the binary adder channel, we show that non-signaling assistance still improves the sum-rate capacity.

In order to find outer bounds, we define a relaxed notion of non-signaling assistance and characterize its capacity region by a single-letter expression, which is the same as the well-known expression for the capacity of the MAC (see Theorem 4.1) except that the inputs $X_1$ and $X_2$ are not required to be independent; see Theorem 4.25. This gives in particular an outer bound on the non-signaling assisted capacity region; see Corollary 4.32. The main open problem that we leave is whether this outer bound on the non-signaling capacity region is tight. We give an example of a channel for which the relaxed notion of non-signaling assistance gives a strictly larger success probability than non-signaling assistance but we do not know if such a gap can persist for the capacity region.

We also study the case where non-signaling assistance is shared only between each sender and the receiver independently. Note that no assistance is shared between the senders. We show that this capacity region is the same as the capacity region without any assistance; see Theorem 4.34 and Corollary 4.35. We note that a similar setting with independent entangled states between each sender and the receiver was studied by Hsieh et al. [HDW08]: a regularized characterization of the capacity region is obtained for any quantum MAC in this setting. It is possible to show using their result that for a classical MAC, this type of entanglement does not change the capacity region given in Theorem 4.1.
**Organization** In Section 4.1, we define precisely the different notions of MAC capacities: the classical capacity (i.e. without any assistance) as well as the non-signaling assisted capacity. In Section 4.2, we show that no polynomial-time constant approximation for multiple-access channel coding exists if a complexity hypothesis on random $k$-SAT formulas is true. In Section 4.3, we address computational complexity questions concerning the probability of success of the best classical coding strategy and the best non-signaling strategy for a MAC. In Section 4.4, we develop numerical methods to find inner bounds on non-signaling assisted capacity regions, and apply those to the binary adder channel and a noisy variant. In Section 4.5, we define our relaxation of non-signaling assistance, we characterize its capacity region by a single-letter formula, and apply those to the binary adder channel. Finally, in Section 4.6, we show that the capacity region with non-signaling assistance shared only between each sender and the receiver independently is the same as without assistance.

# 4.1 Multiple-Access Channels Capacity Regions

## 4.1.1 Classical Capacities

The coding problem for a MAC $W: \mathcal{X}_1 \times \mathcal{X}_2 \to \mathcal{Y}$ can be stated in the following way. We want to encode messages from $[k_1]$ into $\mathcal{X}_1$ and messages from $[k_2]$ into $\mathcal{X}_2$ independently. They are given as inputs to $W$, which results in a random output in $\mathcal{Y}$. From this output, we want to decode back the original messages in $[k_1]$ and $[k_2]$. We will call $e_1: [k_1] \to \mathcal{X}_1$ the first encoder, $e_2: [k_2] \to \mathcal{X}_2$ the second encoder and $d: \mathcal{Y} \to [k_1] \times [k_2]$ the decoder. The scenario is depicted in Figure 4.1.

<figure><img src="image_12.png" /><figcaption>Figure 4.1 – Coding for a MAC $W$.</figcaption></figure>

We want to maximize over all encoders $e_1, e_2$ and decoders $d$ the probability of successfully encoding and decoding the messages through $W$, i.e. the probability that $j_1 = i_1$ and $j_2 = i_2$, given that the input messages are taken uniformly in $[k_1]$ and $[k_2]$. We call this
quantity S(W, k₁, k₂), which is characterized by the following optimization program:

$$
\begin{equation}
\begin{aligned}
S(W, k_1, k_2) &:= \underset{e_1, e_2, d}{\operatorname{maximize}} \quad \frac{1}{k_1 k_2} \sum_{i_1, i_2, x_1, x_2, y} W(y|x_1 x_2) e_1(x_1|i_1) e_2(x_2|i_2) d(i_1 i_2|y) \\
\text{subject to} \quad & \sum_{x_1 \in \mathcal{X}_1} e_1(x_1|i_1) = 1, \forall i_1 \in [k_1] \\
& \sum_{x_2 \in \mathcal{X}_2} e_2(x_2|i_2) = 1, \forall i_2 \in [k_2] \\
& \sum_{j_1 \in [k_1], j_2 \in [k_2]} d(j_1 j_2|y) = 1, \forall y \in \mathcal{Y} \\
& e_1(x_1|i_1), e_2(x_2|i_2), d(j_1 j_2|y) \ge 0
\end{aligned}
\tag{4.1}
\end{equation}
$$

*Proof.* One should note that we allow randomized encoders and decoders for general-
ity reasons, although the value of the program is not changed as it is convex. Besides
that remark, let us name $I_1, I_2, J_1, J_2, X_1, X_2, Y$ the random variables corresponding to
$i_1, i_2, j_1, j_2, x_1, x_2, y$ in the coding and decoding process. Then, for given $e_1, e_2, d$ and $W$,
the objective value of the previous program is:

$$
\begin{align*}
\mathbb{P}(J_1 = I_1, J_2 = I_2) &= \frac{1}{k_1 k_2} \sum_{i_1, i_2} \mathbb{P}(J_1 = I_1, J_2 = I_2 | I_1 = i_1, I_2 = i_2) \\
&= \frac{1}{k_1 k_2} \sum_{i_1, i_2, x_1, x_2} e_1(x_1|i_1) e_2(x_2|i_2) \mathbb{P}(J_1 = i_1, J_2 = i_2 | i_1, i_2, X_1 = x_1, X_2 = x_2) \\
&= \frac{1}{k_1 k_2} \sum_{i_1, i_2, x_1, x_2, y} W(y|x_1 x_2) e_1(x_1|i_1) e_2(x_2|i_2) \mathbb{P}(J_1 = i_1, J_2 = i_2 | i_1, i_2, x_1, x_2, Y=y) \\
&= \frac{1}{k_1 k_2} \sum_{i_1, i_2, x_1, x_2, y} W(y|x_1 x_2) e_1(x_1|i_1) e_2(x_2|i_2) d(i_1, i_2|y). \tag{4.2}
\end{align*}
$$

<figure><img src="image_13.png" /></figure>

The (classical) capacity region of a MAC W, as defined for example in [CT01], can be
reformulated in terms of the previous success probability S using Definition 2.12 and by
C(W) := C[S](W), and its zero-error equivalent is defined by C₀(W) := C₀[S](W).

The capacity region $C(W)$ is characterized by a single-letter formula:

**Theorem 4.1** (Liao [Lia73] and Ahlswede [Ahl73]). *C(W) is the closure of the convex hull of all rate pairs (R₁, R₂) satisfying:*

$$
R_1 < I(X_1 : Y | X_2), R_2 < I(X_2 : Y | X_1), R_1 + R_2 < I((X_1, X_2) : Y),
$$

for $(X_1, X_2) \in \mathcal{X}_1 \times \mathcal{X}_2$ following a product law $P_{X_1} \times P_{X_2}$, and $Y \in \mathcal{Y}$ the outcome of W on inputs $X_1, X_2$.

We will also consider what we call the sum success probability S<sub>sum</sub>(W, k<sub>1</sub>, k<sub>2</sub>), defined using <math><mfrac><mrow><msub><mi>P</mi><mrow><mi>J</mi><mn>1</mn></mrow></msub><mo>=</mo><mrow><msub><mi>I</mi><mn>1</mn></msub></mrow></mfrac><mo>+</mo><mfrac><mrow><msub><mi>P</mi><mrow><mi>J</mi><mn>2</mn></mrow></msub><mo>=</mo><mrow><msub><mi>I</mi><mn>2</mn></msub></mrow></mfrac></mrow></mfrac></math> rather than <math><mfrac><mrow><mi>P</mi><mo>(</mo><msub><mi>J</mi><mrow><mn>1</mn><mo>=</mo><msub><mi>I</mi><mn>1</mn></msub></mrow></mfrac><mo>+</mo><mfrac><mrow><mi>P</mi><mo>(</mo><msub><mi>J</mi><mrow><mn>2</mn><mo>=</mo><msub><mi>I</mi><mn>2</mn></msub></mrow></mfrac></mrow></mfrac></mrow></mfrac></math> as an objective value, which leads