I am currently working on my PhD thesis under the direction of Omar Fawzi in the team MC2 at LIP (ENS de Lyon). I am mainly interested in the algorithmic aspects of quantum communication. I am also interested in information theory in general, as well as approximation algorithms.
M2 in Computer Science, 2016
École Normale Supérieure de Lyon
L3 in Computer Science, 2014
École Normale Supérieure de Lyon
We address the problem of coding for multiple-access channels (MACs) with the assistance of non-signaling correlations between parties. It is well-known that non-signaling assistance does not change the capacity of point-to-point channels. However, it was recently observed that one can construct MACs from two-player non-local games while relating the winning probability of the game to the capacity of the MAC. By considering games for which entanglement (a special kind of non-signaling correlation) increases the winning probability (e.g., the Magic Square game), this shows that for some specific kinds of channels, entanglement between the senders can increase the capacity.
Here, we show that the increase in capacity from non-signaling assistance goes beyond such special channels and applies even to a simple deterministic MAC: the binary adder channel. In particular, we show that, with non-signaling assistance, a sum-rate of $\frac{\log_2(72)}{4} \simeq 1.5425$ can be reached with zero error, beating the maximum classical sum-rate capacity of $\frac{3}{2}$. Furthermore, we show that this capacity increase persists if a small amount of noise is added to the channel.
In order to achieve this, we show that efficient linear programs can be formulated to compute the success probability of the best non-signaling assisted code for a finite number of copies of a multiple-access channel. In particular, this can be used to give lower bounds on the zero-error non-signaling assisted capacity of multiple-access channels.
In the maximum coverage problem, we are given subsets $T_1, \ldots, T_m$ of a universe $[n]$ along with an integer $k$ and the objective is to find a subset $S \subseteq [m]$ of size $k$ that maximizes $C(S) := |\bigcup_{i \in S} T_i|$. It is a classic result that the greedy algorithm for this problem achieves an optimal approximation ratio of $1-e^{-1}$.
In this work we consider a generalization of this problem wherein an element $a$ can contribute by an amount that depends on the number of times it is covered. Given a concave, nondecreasing function $\varphi$, we define $C^{\varphi}(S) := \sum_{a \in [n]} w_{\varphi(|S|^a)}$, where $|S|^a = |{i \in S : a \in T_i}|$. The standard maximum coverage problem corresponds to taking $\varphi(j) = \min(j,1)$. 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{E[\varphi(Poi(x))]}{\varphi(E[Poi(x)])}$. Complementing this approximation guarantee, we establish a matching NP-hardness result when $\varphi$ grows in a sublinear way.
As special cases, we improve the result of Barman et al., IPCO, 2020 about maximum multi-coverage, that was based on the unique games conjecture, and we recover the result of Dudycz et al., IJCAI, 2020 on multi-winner approval-based voting for geometrically dominant rules. Our result goes beyond these special cases and we illustrate it with applications to distributed resource allocation problems, welfare maximization problems and approval-based voting for general rules.
Here, some nice video on Hamming codes