Ali Khalesi

Sajad Daei

Marios Kountouris

Petros Elia
email: petros.elia@eurecom.fr

Multi-User Distributed Computing Via Compressed Sensing

Keywords: Distributed computing, Linearly-separable functions, Compressed sensing, Sparse representation

The multi-user linearly-separable distributed computing problem is considered here, in which N servers help to compute the real-valued functions requested by K users, where each function can be written as a linear combination of up to L (generally non-linear) subfunctions. Each server computes a fraction γ of the subfunctions, then communicates a function of its computed outputs to some of the users, and then each user collects its received data to recover its desired function. Our goal is to bound the ratio between the computation workload done by all servers over the number of datasets.

To this end, we here reformulate the real-valued distributed computing problem into a matrix factorization problem and then into a basic sparse recovery problem, where sparsity implies computational savings. Building on this, we first give a simple probabilistic scheme for subfunction assignment, which allows us to upper bound the optimal normalized computation cost as γ ≤ K N that a generally intractable ℓ0-minimization would give. To bypass the intractability of such optimal scheme, we show that if these optimal schemes enjoy γ ≤ -r K N W -1 -1 (-2K eN r ) (where W-1(•) is the Lambert function and r calibrates the communication between servers and users), then they can actually be derived using a tractable Basis Pursuit ℓ1-minimization. This newly-revealed connection opens up the possibility of designing practical distributed computing algorithms by employing tools and methods from compressed sensing.

I. INTRODUCTION

Distributed computing plays an important role in speeding up non-linear and computationally hard computing tasks. As the complexity of these tasks increases, there is an ever rising need for novel parallel processing techniques that efficiently offload computations to groups of distributed servers. This same complexity increase also brings about many challenges, including, to name a few, computing accuracy [START_REF] Jahani-Nezhad | Codedsketch: A coding scheme for distributed computation of approximated matrix multiplication[END_REF], [START_REF] Wang | Price of precision in coded distributed matrix multiplication: A dimensional analysis[END_REF], scalability [START_REF] Li | A scalable framework for wireless distributed computing[END_REF]- [START_REF] Soleymani | Analog Lagrange coded computing[END_REF], privacy and security [START_REF] Sun | The capacity of private computation[END_REF]- [START_REF] Soleymani | Listdecodable coded computing: Breaking the adversarial toleration barrier[END_REF], and latency and straggler mitigation [START_REF] Raviv | Gradient coding from cyclic mds codes and expander graphs[END_REF]- [START_REF] Behrouzi-Far | Efficient replication for straggler mitigation in distributed computing[END_REF]. There is also substantial research work on various explorations of communication vs. computation trade-off [START_REF] Wan | Distributed linearly separable computation[END_REF], [START_REF] Wan | On the tradeoff between computation and communication costs for distributed linearly separable computation[END_REF], [START_REF] Parrinello | Coded distributed computing with node cooperation substantially increases speedup factors[END_REF], [START_REF] Li | A fundamental tradeoff between computation and communication in distributed computing[END_REF]. Moreover, motivated by the applicability of deriving schemes that work on real numbers, other interesting related settings, such as the Lagrange-coded secret sharing over real numbers [START_REF] Tjell | Privacy in distributed computations based on real number secret sharing[END_REF], coded distributed polynomial evaluation over complex matrices [START_REF] Soleymani | Analog lagrange coded computing[END_REF], [START_REF] Soleymani | Analog secret sharing with applications to private distributed learning[END_REF], as well as the setting of secure distributed multiplication of real or complex matrices [START_REF] Makkonen | Analog secure distributed matrix multiplication over complex numbers[END_REF], have emerged. For a detailed survey of related research works, the interested reader is referred to [START_REF] Ng | A survey of coded distributed computing[END_REF], [START_REF] Li | Coded computing: Mitigating fundamental bottlenecks in large-scale distributed computing and machine learning[END_REF].

This same aforementioned complexity increase, has also brought about various related frameworks such as MapReduce [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF] and Spark [START_REF] Zaharia | Spark: Cluster computing with working sets[END_REF] that apply to broad classes of functions. Focusing on functions over finite fields, the recent work in [START_REF] Khalesi | Multi-user linearly-separable distributed computing[END_REF], [START_REF] Khalesi | Multi-user linearly separable computation: A coding theoretic approach[END_REF] 1 proposed the so-called Multi-User Linearly-Separable Distributed-Computing framework, which allows for distributed computation of functions that adhere to the very broad linearly separable format, which in turn captures various classes of linear and non-linear functions of practical interest 2 . Such functions have the form

F (D 1 , D 2 , . . . , D L ) = L l=1 f l g l (D l )
where D 1 , D 2 , . . . , D L are the L input datasets,W l = g l (D l ) are the computed outputs of basis subfunctions g l (D l ), and f l are scalar coefficients. In the multi-user (K users and N servers) setting where each user asks for its own function, the work in [START_REF] Khalesi | Multi-user linearly-separable distributed computing[END_REF] transformed the distributed computing problem into a simple (preferably sparse) matrix factorization problem over finite fields, and then proceeded to make the direct connection between distributed computing, matrix factorization, and a new coding theoretic approach. In particular, for a K ×L demand matrix F where each row describes the coefficients that define the function requested by a user, the problem was transformed into the factorization problem F = DE, where D and E are the decoding and encoding matrices respectively. E dictated which server should compute which subfunction and then how each server should combine the computed outputs before transmitting, while the K × N decoding matrix D dictated which user should each server communicate to and how each user should combine the various received signals. Then, a solution was proposed that derived from the powerful class of covering codes, and from a new class of so-called partial covering codes. In particular, the parity-check matrix from such codes played the role of D, while then, after considering the columns of F as syndromes, the columns of E were identified as the coset leaders with minimum weight, thus guaranteeing the sparsest E and thus the least computational cost. For example, when D is derived from the basic class of covering codes over a q-ary field, then the corresponding normalized computational cost γ ∈ [0, 1] -describing the fraction of all subfunctions each server had to computetook the form γ = H -1 q (K/N ) where H -1 q (•) is the functional inverse of the entropy function.

We are here though interested in computing functions directly over the reals, which will indeed constitute a substantial deviation from the finite field case. This emphasis on the real (or complex) domain is necessitated by the fact that computing a real-valued problem over a finite field (after discretization) may not be as practical as computing it directly over the reals, mainly because discretization may entail large precision costs and accuracy losses, as well as because finite field computations are notoriously slower than floating point operations. For that, we will consider real-valued functions over L real-valued datasets (or equivalently, with L component/basis subfunctions), and N computing servers and K users each demanding their own function. As we are now working in the field of real numbers, the coding theoretic approach in [START_REF] Khalesi | Multi-user linearly-separable distributed computing[END_REF] does not directly apply, and thus a new approach is required.

Here, our approach is based on establishing, for the first time, a connection between distributed computing and compressed sensing. As a first step, we show (Proposition 1) that there exists an achievable scheme whose normalized computational cost is bounded above as γ ≤ K N . This is a probabilistic scheme, where D is chosen from the Gaussian ensemble, and where the corresponding sparsity of E is the outcome of a randomized process. Then we propose ℓ 0 -minimization, which takes as input D and F to yield a sparse E. This minimization though is generally intractable, and for this reason, we draw from the rich literature of compressed sensing to suggest a more practical approach where we show (Theorem 1) that as long as there exists a scheme whose computational cost is bounded by γ ≤ -r K N W -1 -1 (-2K eN r ) (where W -1 (•) is the Lambert function and r is a parameter that calibrates the communication between servers and users) we can in fact employ a tractable basis pursuit ℓ 1 -minimization to derive such scheme. Notations: For matrices A and B, then [A, B] indicates the horizontal concatenation of the two matrices. We define [n] ≜ {1, 2, . . . , n}. For any matrix X ∈ F m×n , then X(i, j), i ∈ [m], j ∈ [n], represents the entry in the i-th row and j-th column, while X(i, :), i ∈ [m], represents the i-th row, and X(:, j), j ∈ [n] represents the j-th column of X. For two index sets I ⊂ [m], J ∈ [n], then X(I, J ) represents the sub-matrix comprised of the rows in I and columns in J . We will use ∥X∥ 0 to represent the number of nonzero elements of some matrix (or vector) x. Also, ⊗ is the Kronecker product and vec(X) is the vectorization of X.A * represents a conjugate of A. A S represents a matrix that consists of only the columns of A indexed in S ⊂ [N ]. I m×m represents an m×m identity matrix.

II. SYSTEM MODEL AND PROBLEM FORMULATION

We consider the multi-user linearly-separable distributed computation setting (cf. Fig. 1), which consists of K users/clients, N active servers, and a master node that coordinates servers and users. The tasks performed on each server may entail substantial computational complexity as well as time constraints. We consider a setting where each server n can communicate in a single shot (a single time-slot) to some arbitrary user-set T n ⊂ [K], via a dedicated broadcast channel.

In our setting, each user asks for a (generally non-linear) function from a space of linearly-separable functions, where each such function takes several datasets D 1 , . . . , D L as input, and is of the form of a linear combination of individual subfunctions g l (D l ) ∈ R, each taking a single dataset D l as input. Thus, the function

F k (D 1 , . . . , D L ) ∈ R, demanded by user k ∈ [K], is a real-valued function of the form F k (D 1 , D 2 , . . . , D L ) ≜ f k,1 g 1 (D 1 ) . . . + f k,L g L (D L ) (1) = f k,1 W 1 + . . . + f k,L W L ( 2
)
where

W l = g l (D l ) ∈ R, l ∈ [L] is a so-called 'file' output, and f k,l ∈ R, k ∈ [K], l ∈ [L]
are the linear combination coefficients that define each desired function.

A. Phases of the Process

The model involves three phases, with the first being the demand phase, the second being the assignment and computation phase, and the final one the transmission and decoding phase. In the demand phase, each user k ∈ [K] requests F k (•) from the master node, who then deduces the decomposition as in [START_REF] Wang | Price of precision in coded distributed matrix multiplication: A dimensional analysis[END_REF]. Then, based on these K desired functions, during the assignment and computation phase, the master assigns some of the subfunctions to each server n, which then proceeds to compute these and produce the corresponding files W l = f l (D l ) for all the subfunctions f l (D l ), l ∈ W n it is responsible for.

During the transmission phase, each server n ∈ [N ] broadcasts

z n ≜ l∈[L] e n,l W l , n ∈ [N ] (3)
in a single shot its own linear combination of the locally computed output files, and does so to its own particular subset of users T n . The above is defined by the so-called encoding coefficients e n,l ∈ R which are determined by the master. Finally, during the decoding phase, each user k linearly combines the received signals as follows

F ′ k ≜ n∈[N ] d k,n z n (4)
for some decoding coefficients d k,n ∈ R, n ∈ [N ], determined again by the master node. Naturally d k,n = 0, ∀k / ∈ T n . In the end, we say the exact decoding is successful when

F ′ k = F k for all k ∈ [K].

B. Problem Formulation

Similarly to the finite field case, also here, to formulate the problem we use

f ≜ [F 1 , F 2 , . . . , F K ] ⊺ , f k ≜ [f k,1 , f k,2 , . . . , f k,L ] ⊺ , k ∈ [K], w ≜ [W 1 , W 2 , . . . , W L ] ⊺
where f represents the vector of the demanded functions outputs (cf. (2)), f k the vector of function coefficients for user k (cf. ( 2)), and w the vector of output files combined over all subfunctions. We also have e n ≜ [e n,1 , e n,2 , . . . , e n,L ] ⊺ , n ∈ [N ]z ≜ [z 1 , z 2 , . . . , z N ] ⊺ respectively representing the encoding vector at server n, and the overall transmitted vector across all the servers (cf. (3)). Furthermore, we have

d k ≜ [d k,1 , d k,2 , . . . , d k,N ] ⊺ , k ∈ [K]f ′ ≜ [F ′ 1 , F ′ 2 , . . . , F ′ K ]
⊺ respectively representing the decoding vector at user k, and the vector of the decoded functions across all the users. In addition, we have

F ≜ [f 1 , f 2 , . . . , f K ] ⊺ ∈ R K×L , E ≜ [e 1 , e 2 , . . . , e N ] ⊺ ∈ R N ×L , D ≜ [d 1 , d 2 , . . . , d K ] ⊺ ∈ R K×N
where F represents the K × L so-called jobs matrix of all function coefficients across all the users, where E represents the N × L computing and encoding matrix across all servers, and where D represents the K × N decoding matrix across all the users.

Directly from (2), we have that

f = [f 1 , f 2 , . . . , f K ] ⊺ w (5)
and from (3) we have the overall transmitted vector taking the form z = [e 1 , e 2 , . . . , e N ] ⊺ w = Ew.

Furthermore, directly from (4) we have that

F ′ k = d T k z (7)
and thus we have

f ′ = [d 1 , d 2 , . . . , d K ] ⊺ z = Dz. (8)
Recall that we must guarantee

f ′ = f . (9)
After substituting ( 5), ( 6) and ( 8) into ( 9), we see that the above feasibility condition in ( 9) is satisfied if and only if

DEw = Fw. (10)
For this to hold for any w, we must thus have

DE = F. (11)
Note that throughout the whole paper, we assume that K ≤ N .

C. Computational Cost

Recalling quickly that each server n computes the subfunctions whose index are in W n , and since W n = supp(E(n, :)), then the normalized computation cost in our case naturally takes the form

γ ≜ N n=1 |W n | N L = ∥E∥ 0 N L . ( 12
)
As one can see, γ simply describes the average fraction of subfunctions that must be computed by each server, which is also the fraction of non-zero elements in E. It is now clear that decomposing F into the product of two matrices D and sparse E, implies reduced computation cost which results in reduced delay. In particular, the fewer number of nonzero elements in a row of E means less delay in finishing up a task for a server.

III. RESULTS

In this section, we first give a basic probabilistic scheme for subtask assignment, based on employing a Gaussian3 random matrix D, where the scheme employs a simple zero-forcing approach that solves a determined linear system. Albeit basic, this will allow us to upper bound the optimal normalized computation cost -which a generally intractable ℓ 0 -minimization would give -as γ ≤ K N . Proposition 1. For the multi-user linearly-separable distributed computing problem, with K users, N servers and L datasets, employing a random Gaussian D, guarantees that with probability 1, there exists a scheme with bounded normalized computation cost γ ≤ K/N , which serves as an upper bound the ℓ 0 -minimal cost.

Proof. From (11), we have that F(:, l) = DE(:, l), F(:, l) ∈ R K×1 , ∀l ∈ [L] where for each l, in the context of the ℓ 0minimization in [START_REF] Wan | Distributed linearly separable computation[END_REF], we have y = F(:, l), D = A and E(: , l) = z, where again we have an underdetermined system of equations.

Consider choosing L arbitrary random subsets

S l ⊂ [N ], l ∈ [L] where |S l | = K. Now for each l ∈ [L],
we focus on the l -th column E([N ], l) of E and set the elements E([N ]\S l , l) = 0, i.e., from column l, only the elements indexed by S l remain non-zero. Now since

F(:, l) = D([K], [N ]\S l )E([N ]\S l , l) + D([K], S l )E(S l , l),
we get F(:, l) = D([K], S l )E(S l , l), which is a determined system of equations that allows us to determine E(S l , l). In the above, D([K], S l ) is the corresponding K×K submatrix of D. Given the above, each such D([K], S l ) is a K × K Gaussian sub-matrix, which is naturally nonsingular with probability one. Thus, the determined system of equations always has a unique solution for E(S l , l), ∀l ∈ [L], therefore the scheme works for all F (:, l), l ∈ [L]. This scheme guarantees that ∥E(:, l)∥ 0 ≤ K, then ∥E∥ 0 ≤ KL, and thus guarantees that γ ≤ K N . Better performance can be achieved by employing ℓ 0 -minimization as in [START_REF] Wan | Distributed linearly separable computation[END_REF].

As we will discuss in Section IV, ℓ 0 -minimization is known to be NP-hard [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF], hence intractable. To offer a practical solution, the following theorem utilizes results from compressed sensing to describe a range of practical solutions, which now use ℓ 1 -minimisation in order to find -as we will clarify later on -sparse (and unique) encoding matrices E.

Theorem 1. For the multi-user linearly-separable distributed computing problem, with K users, N servers and L datasets, if a scheme exists with a (κ, β) sub-Gaussian random matrix D (cf. Lemma 2) for which ℓ 0 -minimisation would yield

γ ≤ - 1 r K N W -1 -1 (- 2K erN ), 0 ≤ K/N ≤ 12(2β + κ)/κ 2 ,
then the corresponding (and unique) E can be found via basis pursuit ℓ 1 -minimization with probability at least 1 -2e -KL r , where r = 12(4β + 2κ)/κ 2 .

Proof. The proof is provided in the following section, which starts with a brief primer on compressed sensing.

IV. PROOF OF THEOREM 1

Before proceeding with the proof, we quickly describe some basic properties of compressed sensing.

A. Brief Primer on Compressed sensing

We provide here a brief introduction of the compressed sensing results [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF]- [START_REF] Daei | Living near the edge: A lowerbound on the phase transition of total variation minimization[END_REF], which will be employed in our distributed computing problem. We will utilize notation common to the compressed sensing literature, and the link to the computing parameters will be clarified in the next subsection.

As described in [START_REF] Candes | Near-optimal signal recovery from random projections: Universal encoding strategies?[END_REF], compressed sensing seeks to recover a sparse vector x ∈ R p from a few underdetermined linear measurements of the form:

y = Ax ∈ R m (13)
where A ∈ R m×p , m, p ∈ N is the so-called measurement matrix, and y = [y 1 , ..., y m ] T is the measurement vector. In our case, as we will see later on, y will be associated to our computing and encoding matrix E, then A to the communication and decoding matrix D, and x will be associated to the jobs matrix F. The general approach is to recover the sparsest solution via a basic but computationally intractable ℓ 0 -minimization that takes the form

min z∈R p ∥z∥ 0 := p i=1 1 |zi|̸ =0 subject to y = Az (14)
where 1 |zi|̸ =0 denotes the indicator function. This same optimization will lead to the sparsest solution for E and thus will yield the smallest possible γ. To the best of our knowledge, there are no results that enables us to bound the weight of this sparsest solution, and for that we will use a basic constructive approach to bound γ.

The NP-hard nature of the optimization problem in ( 14) has led to the consideration of an ℓ 1 -norm minimization approach, also known as basis pursuit, which is considered as the closest convex tractable alternative for [START_REF] Wan | Distributed linearly separable computation[END_REF], and which is given by

min z∈R p ∥z∥ 1 := p i=1 |z i | (15)
s.t. y = Az. ( 16
)
It is well established in compressed sensing that the estimate x ∈ R p obtained by solving [START_REF] Behrouzi-Far | Efficient replication for straggler mitigation in distributed computing[END_REF], achieves the desired unique solution x as long as some conditions are satisfied 4 . These conditions are closely related to certain properties of the measurement matrix, with one such condition being the well known restricted isometry property (RIP) [START_REF] Candes | Decoding by linear programming[END_REF], which dictates how well ℓ 1 -norm optimization algorithms, such as basis pursuit [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF], can perform. This is captured in the following result, found in [31, Theorem 6.2], which is reproduced here.

Lemma 1. For a matrix A ∈ R m×p and for

δ s (A) ≜ max S⊂[p],|S|≤s ∥A * S A S -I m×m ∥ 2 2→2 (17)
being the sth restricted isometry constant, and if δ 2s (A) < 1 3 , then every s-sparse vector x ∈ R p is the unique solution of minimize z∈R p ∥z∥ 1 subject to Az = Ax.

In particular, the above Lemma shows that having a measurement vector y ∈ R m , where we know apriori that it is a result of a linear system Ax, x ∈ R p , m ≤ p, induced by a unique and s-sparse vector x if δ 2s (A) < 1 3 , then via having a ℓ 1 -minimizer, we can find z as a solution to Az, which it has minimum ∥z∥ 1 , then the above Lemma guarantees that the solution of this minimization is equal to x. The above lemma shows that having δ 2s (A) < 1/3 is sufficient to guarantee the exact recovery of all unique s-sparse vectors via ℓ 1 -minimization. It basically states that if A behaves relatively similar to orthonormal matrices when operating on sparse vectors, then ℓ 1 -minimization will act as an ℓ 0 -minimization.

In our problem here, it is important that we pick D such that A abides by the above property. The following two results tell us directly how to do that. The first, below, is directly adapted from [31, Theorem 9.2]. Lemma 2. Let A ∈ R m×p be an i.i.d. (zero mean, unit variance) sub-Gaussian random matrix with parameters β and κ such that

P(|A i,j | ≥ t) ≤ βe -κt 2 , ∀t > 0. (19)
Then,

δ 2s ( A √ m ) ≤ δ is satisfied with probability at least 1 - 2e -δ 2 m 2c for any δ such that m ≥ 2cδ -2 s ln( ep 2s ) (20)
where

c = 2(4β + 2k) 3k 2 . ( 21
)
Combining Lemma 2 and Lemma 1 after setting δ = 1/3, implies that the uniform recovery of all s-sparse vectors is possible with high probability via the ℓ 1 -minimization in [START_REF] Behrouzi-Far | Efficient replication for straggler mitigation in distributed computing[END_REF] as long as the number of measurements satisfies m ≥ (12(4β+ 2κ)/κ 2 )s ln( ep 2s ) .

B. Proof of Theorem 1

Directly from (11), we have

vec(F) = (D⊗I L×L ) × vec(E), (22)
which matches the compressed sensing setting y = Ax in (13) when considering y = vec(F), A = D⊗I L×L , and x = vec(E), where now m = KL and p = N L. Furthermore, let us also note that directly from [START_REF] Jokar | Sparse solutions to underdetermined kronecker product systems[END_REF], we have

δ s (D ⊗ I L×L ) ≤ δ s (D). (23)
With the elements of D being chosen independently from a zero-mean, unit-variance sub-Gaussian distribution with parameters β, κ (cf. ( 19)), we can now employ Lemma 1 and ( 23), together with Lemma 2 after setting δ 2s < δ = 1/3, to conclude that the exact recovery threshold for a unique E matrix via ℓ 1 -minimization driven by basis pursuit, takes the form

KL ≥ r ∥E∥ 0 ln( eN L 2r ∥E∥ 0 ) (24)
where r = 12(4β + 2κ)/κ 2 . Then after normalizing both sides by N L and applying (12), we get

K N ≥ rγ ln( e 2rγ
).

Let us now define f (x) ≜ -r -1 xW -1 -1 (-2x e ) and evaluate it on the both sides of (25), at x 1 = K/N and x 2 = rγ ln( e 2rγ ) since f (x) is a monotonically increasing function on 0 ≤ x ≤ r/2 and r/2 ≥ x 1 ≥ x 2 ≥ 0, we have f (x 1 ) ≥ f (x 2 ), in the view of the fact that its inverse 5 function is f -1 (x) = rx ln( e 2rx ), we can retrieve the claim. 5 To see this, for g(x) ≜ rx ln( e 2rx ) and f (x) ≜ -r -1 xW -1 -1 (-2x/e), we see that g -1 (x) = f (x) simply because f (g(x)) = -r -1 g(x)W V. DISCUSSION AND CONCLUSION

In the context of our distributed computing problem, it is interesting to observe some of the similarities that exist between the real case (which employed compressed sensing techniques) and the finite-field case in [START_REF] Khalesi | Multi-user linearly-separable distributed computing[END_REF], which employed the structure of covering codes whose covering radius was a measure of the sparsity of the solution for E. For example, in the extreme case of L = q K , the work in [START_REF] Khalesi | Multi-user linearly-separable distributed computing[END_REF] revealed 6the optimal normalized computational cost to be of the form of γ ≃ H -1 q (K/N ), which almost matches γ ≃ K/N in the limit of large q, derived in this paper.

It is also worth noting that our result in Theorem 1 automatically accepts an additional uniqueness propertyon the sparsest solution x in (13) -which is in fact not needed in our distributed computing problem. It would be interesting to explore further improvements in the computational costs, upon the removal of this uniqueness condition. Finally, one can imagine that further improvements in the distributed computing problem could also benefit from the deep connections revealed in [START_REF] Candes | Near-optimal signal recovery from random projections: Universal encoding strategies?[END_REF] between compressed sensing and error correction.

Fig. 1 .

 1 Fig.1. The K-user, N -server, L-Dataset linearly-separable computation setting. Once each user informs the master of its desired functionF k (•), each server n ∈ [N ] computes a subfunction W l = f l (D l ) ∈ R in Wn ⊆ [L].Afterwards, server n broadcasts a linear combination zn (of the locally available computed files) to all users in Tn. This combination is defined by the coefficients e n,l . Finally, for decoding, each user k ∈ [K] linearly combines (based on decoding vectors d k ) all the received signals from all of the servers it has received from. Decoding should produce for each user its desired function F k (D 1 , . . . , D L ).

- 1 - 1 1 - 1 =

 1111 (-2g(x) e ) = -x ln( e 2rx )W --x ln(e/2rx)W -1 -1 ( 2rxe ln(2rx/e)) = -x ln(e/2rx)/ ln(2rx/e) = x.

This work was supported by the European Research Council (ERC) through the EU Horizon 2020 Research and Innovation Programme under Grant 725929 (Project DUALITY) and Grant

(Project SONATA)

Multi-user variant of[START_REF] Wan | Distributed linearly separable computation[END_REF] which generalizes the many distributed computing problems such as gradient coding, matrix-matrix multiplication and etc.

[START_REF] Wang | Price of precision in coded distributed matrix multiplication: A dimensional analysis[END_REF] For more information on this, please see[START_REF] Mallick | Rateless codes for distributed nonlinear computations[END_REF],[START_REF] Mallick | Rateless sum-recovery codes for distributed non-linear computations[END_REF].

This implies that each entry of D is independently and identically picked from a Gaussian distribution.

For our computing problem. these will be conditions in the form of an upper bound on γ.

Over a q-ary alphabet, Hq(x) denotes the entropy function, which takes the form Hq(x) ≜ x log q (q -1) -x log q (x) -(1 -x) log q (1 -x) for all 0 < x < 1 -1/q.


Houda Anoun
email: anoun@labri.fr

Towards a Logical Approach to Nominal Sentences Analysis in Standard Arabic

Standard Arabic (SA) is an extremely rich natural language that has unfortunately received very little interest within computational linguistics literature. We propose in this paper to explore this fertile ground and show the first steps towards the formalization of Arabic syntax and semantics by means of MultiModal Categorial Grammars. We will particularly focus on the analysis of some phenomena related to nominal sentences construction in SA using relevant packages of lexically anchored structural rules.

Introduction

Standard Arabic (SA) is an extensively used Semitic language: it is considered as the official language of more than twenty countries. Although SA's grammar has been studied since the 8 th century by Sibawayh (Sibawayh 1983) among others, very little thorough research work has been done on the formalization of its syntax and semantics. Moreover, all previous studies related to this field either focus on the syntactic level (e.g., using minimalist program [START_REF] Abdel-Hafiz | Verb Agreement in SA: An analysis in the Minimality Program[END_REF]Kremers 2003)), or use linguistic models whose syntax/semantics interface is rather ad-hoc (e.g., using CFG [START_REF] Haddad | A Compositional Approach Towards Semantic Representation and Construction of Arabic LACL[END_REF]). To the best of our knowledge, no attempt has yet been made to capture Arabic syntactic and semantic phenomena within a logical setting. We propose in the following paper to explore this promising direction and describe a fragment of SA by means of MultiModal Categorial Grammars (MMCG) [START_REF] Moortgat | Categorial Type Logic Chapter 2[END_REF]). Our initiative is fruitful since it allows us to take advantage of the transparent interface between syntax and semantics guaranteed by Curry-Howard correspondence. In this paper, we will focus on the analysis of some nominal sentences phenomena in SA (e.g., word order, annexation phenomenon). We will particularly show how to capture such phenomena in an elegant manner using constrained structural reasoning. Our survey aims at consolidating the interrelation between logic and natural languages which undoubtedly has a dual benefit. On the one hand, the use of a rigorous formalism such as MMCG will help us study SA linguistics in a neat and precise fashion. On the other hand, the success of this formalization will confirm the linguistic relevance of MMCG model which proves to be readily adaptable to the specificities of a rich language such as SA.

Preliminaries

2.1 What is MMCG? MMCG [START_REF] Moortgat | Categorial Type Logic Chapter 2[END_REF][START_REF] Oehrle | Multi-Modal Type Logical Grammar Borsley[END_REF]) is a logical system well suited to natural language analysis. This model proved relevant as it allows a neat analysis of complex linguistic phenomena occurring in various natural languages (e.g., Dutch verb clusters [START_REF] Moortgat | Meaningful patterns In Gerbrandy[END_REF], multiple Wh-questions in Serbo-Croatian [START_REF] Vermaat | The Logic of Variation, A cross-linguistic account of wh-question formation PhD thesis[END_REF]). MMCG are composed of two distinct parts: a constant one containing the core logic and a variable one which allows a controlled management of resources. The first part is represented by a deductive system that describes invariants of grammatical form and meaning composition. Furthermore, it is equipped with a compositional construction process for semantics (represented using a simply typed λ-calculus) owing to Curry-Howard correspondence. The underlying logical rules of MMCG are universal as they do not depend upon the words (i.e., grammar terminals) of the chosen natural language. They rather express the way in which such words can combine by using their syntactic types. MMCG handles families of binary type constructors (/ i , \ i , • i ) provided with the structural counterpart (,) i and a set of unary connectives ( j , j ) associated with the structure-forming operator <> j . The categorial slashes represent directional forms of the linear implication, they are used to express grammatical incompleteness. For instance, definite adjectives in SA (e.g., al-mufīd-u, i.e., interesting) take the type np\ 0 np to express their need to combine with a noun phrase to their left to form a modified noun phrase. However, English adjectives (e.g., interesting) take rather the type n/ 0 n as they will merge with a common noun to their right to yield a modified noun. Moreover, unary operators can be used to encode various features such as morphosyntactic ones (e.g., case, gender, number etc) [START_REF] Heylen | Types and Sorts Resource Logic for Feature Checking PhD thesis[END_REF]. Indeed, j A (resp. j A) can be seen as a subtype of A with feature j. For example, we can assign the improved type sg ma np\ 0 np to the adjective 'al-mufīd-u' to explicitly specify that it requires a singular masculine noun phrase. Thus, we are able to avoid the analysis of some ungrammatical phrases such as **(al-qis . at-u almufīd-u, i.e., the interesting-[mas] story-[fem]) which stems from the combination between the previous adjective and a feminine noun phrase. The second part of MMCG encapsulates cross-linguistic variation by means of structural rules which allow controlled reconfigurations of contexts. Structural reasoning is constrained thanks to the use of modes of composition that play a crucial role within this framework [START_REF] Oehrle | Multi-Modal Type Logical Grammar Borsley[END_REF]. Hence, instead of considering a globally available commutativity rule, we can assume that this property is verified by a particular family of connectives marked with mode c. We can control even more this local commutativity by restricting its application to configurations whose left sub-trees are decorated with the structural con-nective <> j . This latter structural rule is formalized by means of the following rewriting rule which can be applied to any appropriate sub-context during a given derivation:

P (c, j) : (< ∆ 1 > j , ∆ 2 ) c → (∆ 2 , < ∆ 1 > j) c
For the sake of legibility, we will rather present structural rules using their axiomatic form as shown below:

P (c, j) : j A • c B → B • c j A
Structural reasoning is a powerful tool; it can be used to capture the flexibility of wordorder in a neat fashion [START_REF] Vermaat | The Logic of Variation, A cross-linguistic account of wh-question formation PhD thesis[END_REF]. Indeed, it allows to relate the different structural positions that a word can occupy within a phrase, thus limiting its lexical ambiguity. Consequently, the application of relevant structural rules makes it possible to derive all the plausible configurations of a given clause from a single type assignment describing the canonical behavior of each one of its components. This asset will be used subsequently to account for word-order variation within SA nominal sentences.

In this paper, we use the natural deduction presentation of MMCG. For the purpose of completeness, the logical rules of this system are presented in Figure 1.1. We recall that the deduction rules operate on sequents like (Γ ⊢ x : A), where Γ is a structured binary context, A is a syntactic category and x is a simply typed λ-term that encapsulates the derivational semantics. The interested reader can find an in-depth survey of this deductive system in [START_REF] Moortgat | Categorial Type Logic Chapter 2[END_REF].

< Γ > j ⊢ a : A Γ ⊢ a : j A i I Γ ⊢ a : A < Γ > j ⊢ a : j A j I (∆ 1 R → ∆ 2 )Γ[∆ 2 ] ⊢ x : C Γ[∆ 1 ] ⊢ x : C S R

Some Words about SA

We present below two important characteristics of SA which are likely to help with the comprehension of our study. More details about SA grammar can be found in [START_REF] Blachère | Eléments de l'Arabe classique Maisonneuve Et Larose eds[END_REF][START_REF] Ryding | A Reference Grammar of Modern Standard Arabic[END_REF][START_REF] Arrajihi | alttat . bīqu 'lnah . wī Dar alnnahd[END_REF]).

• SA is a highly inflectional language: cases are generally marked by means of suffixes (e.g., -u: nominative, -a: accusative and -i: genitive). Moreover, definiteness indicators are incorporated within nouns. In fact, the prefix al-1 is used to form definite nouns while a suffix -n marks indefinite ones. For instance, walad-u-n (i.e., a boy) is an indefinite nominative noun, whereas al-walad-i (i.e., the boy) is a definite genitive one.

• SA is a language with mixed word-order: in fact, word-order in SA can be very flexible in some constructions (e.g., all of SVO, VOS, OVS and VSO orders are generally plausible) but so strict in others (e.g., adjectives always follow their modified nouns). It will be interesting to use controlled structural reasoning to deal with this diversity.

SA writing is built upon a specific alphabet and its direction is from right to left, but for the sake of readability, we will rather use the transliteration given by arabtex2 package.

3 Syntax & Semantics of Nominal Sentences in SA

Basic Nominal Sentences Analysis

In contrast with languages such as English or French, we can build nominal sentences in SA that contain no verb (there is no copulative verb in Arabic such as 'to be' or 'to remain'). This construction is frequently used in other Semitic languages, notably in Hebrew (e.g., ha-sepr gadol, i.e., the book is big). Nominal sentences give descriptions or definitions which are independent of time. They are composed of two components namely a topic realized by a noun phrase with nominative case and a comment which can be either an indefinite noun modifier, an indefinite noun or a prepositional sentence. Examples of grammatical and ungrammatical basic nominal sentences in SA are shown below:

(1) al-mant . iq-u/*mant . iq-u-n

(the) logic-[nom]/logic-[nom] mufīd-u-n interesting-[ind] 'Logic is interesting' (2) mufīd-u-n interesting-[ind] al-mant . iq-u logic-[nom] 'Logic is interesting' (3) al-walad-u the boy-[nom]
fī 'l-bayti in the house 'The boy is in the house' A definite topic (cf. ex. 1-4) can be placed either before or after its comment. Hence, the canonical order puts the emphasis on the definite topic (ex. 1&3), while the inverse order makes it possible to underline the comment (ex. 2&4). However, an indefinite topic can only be used with prepositional comments and should be placed at the end of the sentence (cf. ex. 1&5). In fact, the predicate which occurs after an indefinite noun is considered as an attributive adjective rather than a comment; the resulting construction is than a nominal phrase (of type np) instead of a nominal sentence (of type s3 ). To account for the previous constraints that manage word-order between the topic and its comment in SA, we use controlled structural reasoning. Firstly, we assign to each constituent a single refined type which describes its canonical syntactic behavior and encapsulates its relevant morphosyntactic features4 by means of operator: Composition modes c and c' used in this lexicon are governed by the postulates below:

P (c): A • c B -→ B • c A P (c ′ , def ): ( def A) • c ′ B-→ B • c ′ ( def A)
We notice that both modes c and c' are used to add local commutativity to our system. The commutativity introduced by mode c makes it possible to combine two expressions whose respective order is unconditionally free. In that case, both type constructors / c and \ c represent the same connective namely the non associative linear implication. On the other hand, mode c' introduces commutativity in a constrained fashion thanks to the use of the control operator def . Indeed, its associated structural rule, P (c ′ , def ), cannot be applied unless the first combined expression is definite.

If we consider the grammar provided with the lexicon and postulates above, then we are able to derive the correct examples and predict the ill-formedness of the ungrammatical ones in a straightforward manner. In fact, the underlined idea is as follows. When the comment is a noun modifier (or an indefinite noun), it combines with its definite topic using a commutative mode c, thus allowing the envisaged free word-order. On the other hand, a prepositional comment always searches for its topic to the right and combines with it using mode c'. As the definiteness of the topic required by the prepositional comment is underspecified, a potential topic cannot enter the derivation until its definiteness feature is checked (i.e., by means of E rule). If the topic is definite (i.e., at this stage, it should be decorated by the structural operator <> def ), then it can move to the beginning of the sentence thanks to P (c ′ , def ) postulate; otherwise, no displacement proves to be possible. These steps are illustrated in the derivation of sentence 3 below:

fī ′ lbayti ⊢ f : s/ ′ c nom np Ax alwaladu ⊢ w : def nom np Ax < alwaladu > def ⊢ w : nom np def E (fī ′ lbayti, < alwaladu > def ) c ′ ⊢ (f w) : s / c ′ E (< alwaladu > def , fī ′ lbayti) c ′ ⊢ (f w) : s P (c ′ , def )
The derivational semantics of a sentence is computed in tandem with its syntactic derivation thanks to Curry-Howard correspondence. For instance, the deduction associated to sentence 3 yields the term (f w), where f (resp. w) represents the semantics of al-waladu (resp. fī 'lbayti ). The final semantics of this sentence, namely the logical formula in(ι man, ι house)5 , results from substituting each formal variable representing a linguistic entity by its lexical semantics.

Towards Complex Nominal Sentences Annexation Phenomenon

All topics so far have been simple noun phrases. We will see in this section how we can enhance our nominal sentences by using compound topics. In SA, we can form compound noun phrases by means of annexation phenomenon [START_REF] Blachère | Eléments de l'Arabe classique Maisonneuve Et Larose eds[END_REF]Kremers 2003). These compound nouns have the following form 'cn=n 1 n 2 ... n k ' (k ≥ 2), where each n j (1≤j<k) is a noun in construction state (i.e., which has neither the definite nor the indefinite indicator), whereas n k is a noun phrase (either definite or indefinite). The resulting compound noun 'cn' inherits the definiteness feature from n k , whereas its case is the same as n 1 (all the other nouns n j (j≥2) take the genitive case).

Here are some examples of noun phrases built using annexation: Hence, al-nouns and nn-nouns are both complete and self-contained as they can be used in several contexts (as subjects or topics etc). Nevertheless, cs-nouns are incomplete; they are only used to build compound noun phrases. They are assigned a functional type since they require to combine with a noun phrase to their right by means of a rigid composition mode 0 (i.e., non-associative and non-commutative mode) to yield a complete expression.

We consider the grammar that supports the following package of postulates, R= K(def) ∪ K(ind) ∪ Inc(def, al) ∪ Inc(ind, nn), where:

K(j): j (A • 0 B) -→ cs A • 0 j B Inc(i, j): i A -→ j B
The structural rule K(def) (resp. K(ind)) is a kind of strong distributivity postulate [START_REF] Heylen | Types and Sorts Resource Logic for Feature Checking PhD thesis[END_REF]. Intuitively, this postulate stipulate that a complex constituent is definite (resp. indefinite) if its head is in construction state (e.g., cs-noun) and its complement is definite (resp. indefinite). However, the rule Inc(def, al) (resp. Inc(ind, nn)) is nothing else but an inclusion principle. It states that all al-nouns (resp. nn-nouns) are inevitably definite (resp. indefinite).

Owing to the package R, only well-formed compound nouns 'n 1 ...n k ' can be derived, they are assigned either type ' def c 1 np' if n k is an al-noun or type ' ind c 1 np' if n k is a nn-noun (c 1 is the case of n 1 ). In fact, the package R makes it possible to apply the lock/key strategy [START_REF] Moortgat | Meaningful patterns In Gerbrandy[END_REF] which, in our case, proceeds as the following. Firstly, recursive rules K(j) are used to open each lock cs surrounding nouns n i (1≤i<k)6 , thus checking that they are all in construction state. Secondly, Inc(i, j) rules are used to check definiteness feature of noun n k . Finally, the derivation can be completed by a succession of / 0 elimination. Therefore, it is easy to parse a compound nominal sentence such as 's 1 =֓ibnu 'l-mudarris-i fī 'lbayti ' (i.e., the man's son is in the house), the crucial steps of its topic's derivation are sketched below:

ibnu : cs ( nom np/ 0 gen np) ⊢ i : cs ( nom np/ 0 gen np) Ax < ibnu : cs ( nom np/ 0 gen np) > cs ⊢ i : nom np/ 0 gen np cs E ′ lmudarrisi : al gen np ⊢ m : al gen np Ax < ′ lmudarrisi : al gen np > al ⊢ m : gen np cs E (< ibnu : cs ( nom np/ 0 gen np) > cs ,< ′ lmudarrisi : al gen np > al ) 0 ⊢ (im) : nom np / 0 E (< ibnu : cs ( nom np/ 0 gen np) > cs ,< ′ lmudarrisi : al gen np > def ) 0 ⊢ (im) : nom np Inc(def, al) < (ibnu : cs ( nom np/ 0 gen np), ′ lmudarrisi : al gen np) 0 > def ⊢ (im) : nom np K(def ) (ibnu : cs ( nom np/ 0 gen np), ′ lmudarrisi : al gen np) 0 ⊢ (im) : def nom np def I
Finally, we use higher order λ-terms7 to represent the lexical semantics of each class of SA nouns. For instance, singular SA nouns are assigned the following meanings: cs-noun:

λP (e→t)→t λQ e→t . ∃ x. w pred (x) ∧ Q(x) ∧ w cs (Rel) P(λy. Rel(x,y) ∧ ∀ z. w pred (z) ∧ Rel(z,y) ⇒ z=x) al-noun: w al λQ e→t . ∃ x. w pred (x) ∧ Q(x) ∧ (∀ z. w pred (z) ⇒ z=x) nn-noun: w n λQ e→t . ∃ x. w pred (x) ∧ Q(x)
Note that the semantics of each noun w x is based upon a predicate w pred representing a set of individuals that share a specific property (e.g., teacher, son...). Moreover, the meaning of cs-nouns closely depends on a relation Rel that binds these individuals to their annexed objects (e.g., Rel can be either a relation of possession, family-ship ...). Lastly, it is worth noticing that both cs-nouns and al-nouns meanings require uniqueness conditions. For instance, the semantics of a cs-noun w cs stipulates that the intersection between the set of individuals verifying the property w pred and the range of entities connected to the annexed object by the relation Rel is nothing else but a singleton. Using the previous lexical semantics, one can easily check that the meaning of sentence s 1 is represented by the following first-order formula: ∃x. son(x) ∧ in(x, ι house) ∧ ∃y. teacher(y) ∧ family-ship(x,y) ∧ (∀ z. son(z) ∧ family-ship(z,y) ⇒ z=x) ∧ (∀z. man(z) ⇒ z=x) Our study can also be applied to account for nouns built using annexation in Hebrew. In fact, this phenomenon is managed by the same range of syntactic principles in both Hebrew and SA as shows the following example quoted from [START_REF] Wintner | Definiteness in the Hebrew Noun Phrase[END_REF]:

(9) yaldei children-[cs] mnahhel manager-[cs] taxnot stations-[cs]
ha-rakkebt the train 'the train stations manager's children'

Adjectives

We distinguish two classes of adjectives in SA, namely attributive adjectives and predicative ones. Attributive adjectives are used to modify definite and indefinite nouns, they can be involved in the construction of enhanced topics. These adjectives agree with the head they modify on number, gender, case and definiteness. However, predicative adjectives are used as comments within nominal sentences; they are always indefinite and they agree with their topic on gender and number. We present in the following some examples of well-formed and ill-formed SA clauses involving the use of adjectives: 'l-֒aynayn-i the eyes-[gen] 'the teacher has beautiful eyes' Unlike some languages where the word-order between adjectives and their head is relatively free (e.g., French), SA attributive adjectives are post-modifiers, they always occur after the noun phrase they modify. Moreover, when the noun phrase is built using annexation, the adjective should be placed at the end of the whole construction (cf. ex. 10) since nouns in construct state cannot be modified (cf. ex. 11). On the other hand, we are able to build enhanced adjectival phrases thanks to annexation phenomenon (cf. ex. 12&13). In SA, an adjectival phrase has two constituents. The first one (i.e., the head) is either a cs-adjective (adjective in construct state) or an al-adjective (simple definite adjective) whereas the second one (i.e., the complement) is nothing else but a genitive al-noun. Hence, it is forbidden to build an adjectival phrase by combining an adjective with a compound noun phrase (cf. ex. 12). The following table recapitulates the various syntactic constraints which manage the use of SA adjectives. For the sake of legibility, we only focus on definiteness and case agreements between adjectives and their heads; gender and number agreements can be added in a straightforward fashion.

A 1 = def case np\ 0 def case np A 2 = ind case np\ 0 ind case np A 3 = A 2 / 0 al gen np A ′ 1 = A 1 / 0 al gen np
Thanks to this type assignment, we are able to handle the different uses of SA adjectives in a rigorous manner. Lexical ambiguity is necessary to account for the distinct syntactic behaviors of some adjectives. For instance, al-adjectives can directly combine with their definite nouns (e.g., ' l-gamīl-u in ex. 10); in that case we use the syntactic type A 1 . Otherwise, these adjectives can initially form an adjectival phrase by combining with a genitive al-noun to their right and then merge with their head to the left (e.g., ' l-gamīl-u in ex. 12). This latter case is dealt with by means of the second syntactic type A ′ 1 .

The semantics of SA adjectives resembles the semantics of English adjectives at a great extent. The interested reader can find more details about this field in [START_REF] Chierchia | Meaning and Grammar, An Introduction to Semantics The MIT press[END_REF].

Negation

In contrast with some languages where negation is a slightly complex phenomenon (e.g., negation in French involves a discontinuous constituent ne ... pas), nominal sentences negation in SA is obtained in a straightforward fashion. This is done by adding the particle mā at the start of the sentence as illustrated below: 'lassa֒ādat-i the happiness-[gen] 'Money is not the source of happiness' Consequently, we can easily deal with nominal sentences negation in MMCG by assigning the syntactic type s/ 0 s to the particle mā. The negation of SA nominal sentences can also be obtained by using some external governors such as laysa [START_REF] Blachère | Eléments de l'Arabe classique Maisonneuve Et Larose eds[END_REF][START_REF] Arrajihi | alttat . bīqu 'lnah . wī Dar alnnahd[END_REF]). This latter particle also precedes the nominal sentence but it changes the default case of its comment as shows the following example: Since the external governor laysa does not subcategorize for a whole nominal sentence, we will not be concerned with its formal study in this work.

Conclusion & Prospects

In this paper, we presented the first steps towards the syntactic and semantic analysis of SA using MMCG formalism. In particular, we showed that we can deal with simple and compound nominal sentence constructions using appropriate structural modules. Moreover, the meaning of these sentences is obtained in a compositional fashion thanks to the use of simply typed λ-calculus and Curry-Howard correspondence. The complete study also includes a logical treatment of the asymmetry between the different forms of verbal phrases in SA. This latter work will be described in a forthcoming paper. Our ultimate goal is to build a compact MMCG grammar which handles a decent fragment of SA containing at least the frequent linguistic phenomena, e.g., ellipsis, coordination, wh-questions and anaphora. Moreover, we intend to extend our work and deal with some Arabic dialects used in different speech communities (e.g., Moroccan and Egyptian). We also plan to compare Arabic phenomena with other Semitic languages, notably Hebrew. We hope that the present survey will constitute the pillar of the formal study of crosslinguistic variation between the various forms of Arabic Language.

Figure 1 . 1 :

 11 Figure 1.1: Natural deduction rules for Multimodal Logic

( 4 )

 4 fī 'l-bayti in the house 'l-walad-u the boy-[nom] 'The boy is in the house' (5) fī 'l-bayti in the house walad-u-n, a boy *walad-u-n fī 'l-bayti 'A boy is in the house'

( 6 )

 6 ֓ibn-u/*al-֓ibn-u son-[nom]/the son-[nom] 'l-mudarris-i the teacher-[gen] 'the son of the teacher' (7) kitāb-u/*kitāb-u-n book-[nom]/a book-[nom]

  ֒aynayn-i/*lawn-u 'l-֒aynayn-i the eyes-[gen]/*color-[nom] the eyes 'the teacher with beautiful eyes' (13) 'l-mudarris-u the teacher-[gen] gamīl-u beautiful-[nom]

  To capture annexation phenomenon within MMCG, we assign a suitable syntactic type to each one of the three classes of SA nouns, namely al-nouns (definite simple nouns), csnouns (nouns in construction state) and nn-nouns (indefinite simple nouns).

	(8) kitāb-u	֓ibn-i	'l-mudarris-i
	book-[nom]	son-[gen]	the teacher-[gen]
	'the book of the teacher's son'
		al-nouns	nn-nouns	cs-nouns
		al case np	nn	case np
				mudarris-i-n
				a teacher-[gen]
	'the book of a teacher'

cs ( case np / 0 gen np)

  P 2 = def nom np\ c s P 3 = P 2 / 0 al gen np

	SA adjectives	al-adjectives	nn-adjectives	cs-adjectives
	Attributive

Predicative ×

x :A⊢x : A Ax ∆ ⊢ p : A • i BΓ[(a : A, b : B) i ] ⊢ y : C Γ[∆] ⊢ y[a := Π 1 (p), b := Π 2 (p)] : C • i E Γ ⊢ f : A/ i B∆ ⊢ b : B (Γ, ∆) i ⊢ (f b) : A / i E Γ ⊢ b : B∆ ⊢ f : B\ i A (Γ, ∆) i ⊢ (f b) : A \ i E Γ ⊢ a : A∆ ⊢ b : B (Γ, ∆) i ⊢ (a, b) : A • i B • i I (Γ, x : B) i ⊢ f : A Γ ⊢ λx.f : A/ i B / i I (x : B, Γ) i ⊢ f : A Γ ⊢ λx.f : B\ i A \ i I ∆ ⊢ x : j AΓ[< a : A > j ] ⊢ c : C Γ[∆] ⊢ c[a := x] : C i E Γ ⊢ a : j A < Γ > j ⊢ a : A j E

The prefix al-becomes 'l-when the noun occurs after a word ending with a vowel

Available at www.informatik.uni-stuttgart.de/ifi/bs/research/arab e.html

In all this paper, the atomic type s represents well-formed nominal sentences

Each np is decorated by its definiteness feature (def, ind) followed by its case feature

Recall that ι, the description operator, is of type (e→t)→e and (ι P) returns the only individual that verifies the property P

The key cs allows to open cs lock since cs cs A ⊢ A

To preserve the form-meaning correspondence, we will assume that the syntactic type np is lifted to (s/ 0 np)\ 0 s

Acknowledgements

I would like to thank my father Abdelhamid Anoun as well as my colleagues Youssef Tahir and Dina El kassas for fruitful discussions about SA linguistics. I am also very grateful to the anonymous ESSLLI reviewers for their useful comments and constructive suggestions. Finally, I am deeply indebted to my parents, my sister Soumaya and my fiancé Réda for their psychological support and everlasting care. Of course, all remaining errors and omissions are mine.


Federico Brunero
email: brunero@eurecom.fr

Petros Elia
email: elia@eurecom.fr

Coded Caching Does Not Generally Benefit From Selfish Caching

Keywords: Coded caching, file popularity, index coding, information-theoretic converse, selfish caching

In typical coded caching scenarios, the content of a central library is assumed to be of interest to all receiving users. However, in a realistic scenario the users may have diverging interests which may intersect to various degrees. What happens for example if each file is of potential interest to, say, 40 % of the users and each user has potential interest in 40 % of the library? What if then each user caches selfishly only from content of potential interest? In this work, we formulate the symmetric selfish coded caching problem, where each user naturally makes requests from a subset of the library, which defines its own file demand set (FDS), and caches selfishly only contents from its own FDS. For the scenario where the different FDSs symmetrically overlap to some extent, we propose a novel information-theoretic converse that reveals, for such general setting of symmetric FDS structures, that selfish coded caching yields a load performance which is strictly worse -in the non-trivial memory regimethan that in standard coded caching.

I. INTRODUCTION

The explosion of network traffic in the recent years has sparked much interest in new communication techniques with the purpose of reducing the traffic load. In this context, caching has always played a key role in bringing contents closer to their destinations, thus reducing the volume of the communication problem during peak hours. Coded caching [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] has been proposed as a clever way to better exploit caching capabilities of receiving users, where such coded technique represents, in comparison to traditional prefetching, a key breakthrough in the way end-user caches are employed to change both the volume of the communication problem and the structure of the problem itself. Current research on coded caching encompasses many topics such as the role of multiple antennas in caching [START_REF] Parrinello | Fundamental limits of coded caching with multiple antennas, shared caches and uncoded prefetching[END_REF]- [START_REF] Tölli | Multi-antenna interference management for coded caching[END_REF], the interplay between caching and file popularity [START_REF] Zhang | Coded caching under arbitrary popularity distributions[END_REF]- [START_REF] Hachem | Coded caching for multi-level popularity and access[END_REF], and a variety of other scenarios [START_REF] Lampiris | Full coded caching gains for cache-less users[END_REF]- [START_REF] Zhao | Vector coded caching multiplicatively boosts the throughput of realistic downlink systems[END_REF]. For a thorough review of the existing coded caching works, we strongly encourage the reader to refer to the longer version of this work [START_REF] Brunero | Unselfish coded caching can yield unbounded gains over symmetrically selfish caching[END_REF].

A. Heterogeneous User Profiles and Selfish Coded Caching

If on one hand a key ingredient in standard prefetching systems has commonly been the exploitation of the fact that some contents are more popular than others, and thus are generally to be allocated more cache space, on the other we This work was supported by the European Research Council (ERC) through the EU Horizon 2020 Research and Innovation Program under Grant 725929 (Project DUALITY). An extended version of this work [START_REF] Brunero | Unselfish coded caching can yield unbounded gains over symmetrically selfish caching[END_REF] has been submitted to IEEE Transactions on Information Theory. are just beginning to explore the interplay between coded caching, heterogeneous preferences and selfish caching, where by selfish caching we refer to caching policies where each user caches only contents from its own set of individual preferences.

Recent works have sought to explore this interplay. For example, in the context of coded caching with users having heterogeneous content preferences, the work in [START_REF] Wang | Coded caching with heterogeneous user profiles[END_REF] analyzed the peak load of three different coded caching schemes that account for the user preferences, revealing occasional performance gains that are similarly dependent on the structure of these preferences. Related analysis appears in [START_REF] Zhang | On the average rate for coded caching with heterogeneous user profiles[END_REF], now for the average load of the same schemes in [START_REF] Wang | Coded caching with heterogeneous user profiles[END_REF]. On the other hand, the work in [START_REF] Chang | Coded caching with heterogeneous file demand sets -the insufficiency of selfish coded caching[END_REF] focused on finding instances where unselfish coded caching outperforms selfish designs. This work nicely considered the performance of selfish coded caching in the context of heterogeneous file demand sets (FDSs), cleverly employing bounds to show that, for the case of K = 2 users and N = 3 files, unselfish designs strictly outperform selfish designs in terms of communication load, albeit only by a factor of up to 14 %. In addition, the notable work in [START_REF] Chang | On coded caching for two users with overlapping demand sets[END_REF] established, under the assumption of selfish and uncoded prefetching, the optimal average load for the case of K = 2 users and a variety of overlaps between the two users' profiles, also providing explicit prefetching schemes of a selfish nature. In a similar vein, the recent work in [START_REF] Wan | On the optimal load-memory tradeoff of coded caching for location-based content[END_REF] considered the scenario where users are interested in a limited set of contents depending on their location. To the best of our knowledge, the above constitutes the majority of works on selfish coded caching.

B. Main Contributions

First, we propose a novel symmetric FDS structure which aims to regulate the selfishness effect and to encapsulate the aspect of overlapping of interests by calibrating the degree of separation between the interests of the users. Secondly, we develop an information-theoretic converse on the optimal worst-case load under the assumption of uncoded and selfish placement. The interesting outcome of such bound is that selfish coded caching can be rather detrimental. In [START_REF] Brunero | Unselfish coded caching can yield unbounded gains over symmetrically selfish caching[END_REF] we also provide instances where this bound is found to be tight.

C. Paper Outline

The system model is presented in Section II. Section III presents the information-theoretic converse, whose main proof in Section III-A is followed by the clarifying example in Section III-B. Section IV concludes the paper.

D. Notation

We denote by Z + the set of positive integers. For n ∈ Z + , we define [n] := {1, 2, . . . , n}. If a, b ∈ Z + such that a < b, then [a : b] := {a, a + 1, . . . , b -1, b}. For sets we use calligraphic symbols, whereas for vectors we use bold symbols. Given a finite set A, we denote by |A| its cardinality. We denote by n k the binomial coefficient and we let n k = 0 whenever n < 0, k < 0 or n < k. We use m mod n to denote the modulo operation on m with integer divisor n, letting m mod n = n when n divides m. For n ∈ Z + , we denote by S n the group of all permutations of [n] and by H n the group of circular1 permutations of [n]. To simplify, we denote by π n := (π(1), . . . , π(n)) the vector of elements from [n] permuted according to π ∈ S n and we let π -1 denote the inverse function of π.

II. SYSTEM MODEL

We consider the centralized caching scenario in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] where one central server has access to a library L containing N files of B bits each. This server is connected to K users through a shared error-free broadcast channel, and each user is equipped with a cache of size M files or, equivalently, M B bits.

The system works in two phases, i.e., the placement phase and the delivery phase. During the placement phase, the enduser caches are filled by the server according to a caching policy without any knowledge of future requests. During the delivery phase, after the demands of the users are simultaneously revealed, the server sends coded messages over the shared link to deliver the missing information to each user. Assuming that in the delivery phase each user demands simultaneously one file, the worst-case communication load R is defined as the total number of transmitted bits, normalized by the file-size B, that can guarantee delivery of all requested files in the worst-case scenario. The optimal worst-case communication load R ⋆ is then formally defined as

R ⋆ (M ) := inf{R : (M, R) is achievable} (1)
where the tuple (M, R) is said to be achievable if there exists a caching-and-delivery scheme which guarantees, for any possible demand, a load R for a given memory value M .

To capture the interplay between coded caching, heterogeneous interests and selfish caching, we propose an FDS structure that allows to calibrate the degree of separation between the interests of the different users.

Definition 1 (The Symmetric (K, α, F ) FDS Structure). Let α ∈ [K] and F ∈ Z + . The symmetric (K, α, F ) FDS structure assumes an N -file library L = {W S : S ⊆ [K], |S| = α} to be a collection of disjoint file classes W S = {W f,S : f ∈ [F ]},
where each class W S consists of F different files and each of such files is of interest to the α users in the set S. As a consequence, the FDS of each user k ∈ [K], which describes the files this user is potentially interested in, is defined as

F k = {W S : S ⊆ [K], |S| = α, k ∈ S} . (2)
We can see from the above that the library is partitioned into

C = K α disjoint classes of files, each composed of F files, for a total of N = F C files. Each user k ∈ [K] is then interested in its own FDS, which is made of F K-1 α-1 files for each k ∈ [K].
Each file class is identified by an α-tuple S, where S simply tells which α users are interested in the file class W S . We focus on the regime N ≥ K, which is equivalent to F ≥ ⌈K/C⌉ for any fixed K and α. The following example can help familiarize the reader with the notation.

F 1 = {W 123 , W 124 , W 134 } F 3 = {W 123 , W 134 , W 234 } (3) F 2 = {W 123 , W 124 , W 234 } F 4 = {W 124 , W 134 , W 234 } (4)
where each FDS consists of 6 files in total. For F k denoting the FDS of user k ∈

[4], user 1 is interested in files in F 1 = {W f,S : S ⊆ [4], |S| = 3, 1 ∈ S, f ∈ [2]}, user 2 is interested in files in F 2 = {W f,S : S ⊆ [4], |S| = 3, 2 ∈ S, f ∈ [2]},
and so on.

Deviating from standard notation practices, we will use the double-index notation W f k ,D k to denote the file requested by user k. Hence, any demand will be described by the tuple (d, f )

with d = (D 1 , . . . , D K ) and f = (f 1 , . . . , f K ). Trivially, it holds that W f k ,D k ∈ F k for each k ∈ [K].
Our goal is to provide a converse bound on the optimal worst-case load under the assumption of uncoded and selfish placement, whose definition is given in the following.

Definition 2 (Uncoded and Selfish Cache Placement). A cache placement is uncoded if the bits of the files are simply copied within the caches of the users and is selfish when it guarantees for each k ∈ [K] that a subfile of W f,S can be cached at user k only if W f,S ∈ F k , i.e., only if the file W f,S is potentially of interest to user k.

We denote by R ⋆ u,s the optimal worst-case load under uncoded and selfish placement, and by R MAN the load of the Maddah-Ali and Niesen (MAN) scheme in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF].

III. MAIN RESULTS

The converse bound employs the index coding techniques of [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF] that proved the optimality of the MAN scheme under uncoded prefetching. Our main challenge will be to adapt the approach in [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF] to reflect the system model in Section II. The result is stated in the following theorem, whereas the proof is presented in Section III-A.

Theorem 1. Under the assumption of uncoded and selfish cache placement, and given the symmetric (K, α, F ) FDS structure, the optimal worst-case communication load R ⋆ u,s is lower bounded by R LB which is a piecewise linear curve with corner points

(M, R LB ) = t N K , α t+1 + (K -α) α-1 t α t , ∀t ∈ [0 : α]. (5)
The converse bound presented here shows that adding the selfish cache placement constraint implies a higher optimal communication load compared to the unselfish scenario. This is nicely reflected in the following3 corollary.

Corollary 1.1. Given the symmetric (K, α, F ) FDS structure and α ∈ [2 : K -1], the converse reveals that

R ⋆ u,s (t) R MAN (t) ≥ 1, ∀t ∈ [0 : α -1] (6)
R ⋆ u,s (t) R MAN (t) > 1, ∀t ∈ [α -2]. (7)
For the (K, α, F ) FDS structure and in the non-trivial range t ∈ [0 : α-1], selfish coded caching is not better than unselfish coded caching, while optimal unselfish coded caching, in the non-extremal points of t and under uncoded placement, strictly outperforms any implementation of selfish coded caching.

Proof. Due to lack of space, the proof is relegated to the longer version of this work [START_REF] Brunero | Unselfish coded caching can yield unbounded gains over symmetrically selfish caching[END_REF].

Notice that Corollary 1.1 holds under the considered (K, α, F ) FDS structure. Hence, we cannot state that selfish caching is detrimental for any conceivable FDS structure and for any memory point. However, in light of the results in Theorem 1 and Corollary 1.1, our claim is that selfish caching can be rather detrimental.

A. Main Proof

The derivation of the converse makes extensive use of the connection between caching and index coding identified in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] and successfully exploited in [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF]. Briefly, we recall that an index coding problem [START_REF] Bar-Yossef | Index coding with side information[END_REF] consists of a server wishing to deliver N ′ independent messages to K ′ users via a basic bottleneck link. Each user k ∈ [K ′ ] has its own desired message set M k ⊆ [N ′ ] and has knowledge of its own side information set

A k ⊆ [N ′ ].
The index coding problem can be described by the side information graph, a directed graph where each vertex is a message M i for i ∈ [N ′ ] and where there is an edge from M i to M j if M i is in the side information set of the user requesting M j . The derivation of our converse will make use of the following result from [START_REF] Arbabjolfaei | On the capacity region for index coding[END_REF]Corollary 1].

Lemma 1 ([19, Corollary 1]). In an index coding problem with N ′ messages M i for i ∈ [N ′ ], the minimum number of transmitted bits ρ is lower bounded as

ρ ≥ i∈J |M i | (8)
for any acyclic subgraph J of the side information graph.

We provide the proof for the non-trivial range 4 α ∈ [2 : K -1] and for the range t ∈ [0 : α]. Indeed, for t = α we have M = αN/K = F K-1 α-1 , so the point (M, R) = (αN/K, 0) is trivially achievable as a consequence of each user being able to store the entirety of its FDS.

Since each file is of interest to α users, the first step toward the converse consists of splitting each file in a generic manner into a maximum of 2 α disjoint subfiles as

W f,S = {W f,S,T : T ⊆ S} (9)
for each S ⊆ [K] with |S| = α and for each f ∈ [F ], where W f,S,T is the subfile of W f,S cached exactly and only by users in T . Such generic splitting satisfies the uncoded and selfish placement constraint as defined in Definition 2. 1) Constructing the Index Coding Bound: Assuming that each user requests a distinct file, we can now identify the index coding problem with K ′ = K users and N ′ = K2 α-1 messages, such that for any tuple (d, f ) the desired message set and the side information set are respectively given by

M k = {W f k ,D k ,T : T ⊆ D k , k / ∈ T } and A k = {W f,S,T : f ∈ [F ], S ⊆ [K], |S| = α, T ⊆ S, k ∈ T } for each user k ∈ [K].
To apply Lemma 1, we are interested in acyclic sets of vertices J in the side information graph of the problem. In the spirit of [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF], we know that the set

k∈[K] T ⊆(([K]\{u1,...,u k })∩Du k ) W fu k ,Du k ,T (10)
does not contain any directed cycle for any demand (d, f ) and any vector u, where u = π K for some π ∈ S K . Consequently, applying Lemma 1 yields the following lower bound

BR ⋆ u,s ≥ R(d, f , u) (11)
where R(d, f , u) is defined as

R(d, f , u) := k∈[K] T ⊆(([K]\{u1,...,u k })∩Du k ) W fu k ,Du k ,T . (12
) 2) Constructing the Optimization Problem: Our goal is to create several bounds as the one in [START_REF] Brunero | Unselfish coded caching can yield unbounded gains over symmetrically selfish caching[END_REF] and eventually average all of them to obtain a useful lower bound on the optimal worst-case load. We aim to create a bound for a set C of properly selected demands and for a set U (d,f ) of properly selected permutations for each demand (d, f ) ∈ C. Hence, we aim to simplify the expression given by

(d,f )∈C u∈U (d,f ) BR ⋆ u,s ≥ (d,f )∈C u∈U (d,f ) R(d, f , u). ( 13
)
Remark 1. The careful selection of the demand set C and permutation set U (d,f ) for each (d, f ) ∈ C is a pivotal difference with respect to the procedure in [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF]. Indeed, if one develops a converse bound following the exact same procedure in [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF], then the resulting bound is looser than the one presented in this paper. Finding the good set of demands and permutations becomes the key to obtaining a tighter bound while keeping the problem analytically tractable.

For a permutation π ∈ H K , we consider the demands (d, f ) where

D k = {k, π((π -1 (k) + 1) mod K), . . . , π((π -1 (k) + α -1) mod K)} and f k ∈ [F ] for each k ∈ [K].
There is a total of F K such demands. Considering that the order of H K is (K -1)! and that we take F K demands for each π ∈ H K , we consider (K -1)!F K distinct 5 demands in total, denoting by C the set of such demands. Since the vector d depends on some circular permutation π ∈ H K , we will identify from now on each demand with (d π , f ) ∈ C to highlight such dependency. For a demand (d π , f ) ∈ C, we let U (dπ,f ) be the set containing the K circular shifts of π K .

Toward simplifying the expression in ( 13), we count how many times each subfile W f,S,T -for any f ∈ [START_REF] Zhang | On the average rate for coded caching with heterogeneous user profiles[END_REF]. To this end, we need the following lemma.

[F ], S ⊆ [K] with |S| = α, T ⊆ S and |T | = t ′ with t ′ ∈ [0 : α] -appears in
Lemma 2. Let π ∈ S K be a permutation of the set [K]. Consider k 1 , k 2 ∈ [K] such that k 1 ̸ = k 2 . Consider ℓ = (π -1 (k 2 ) -π -1 (k 1 )) mod K. ( 14
)
Then, out of the K circular shifts of π K , there is a total of (K -ℓ) of them such that k 1 appears before k 2 .

Proof. Due to lack of space, the proof is relegated to the longer version of this work [START_REF] Brunero | Unselfish coded caching can yield unbounded gains over symmetrically selfish caching[END_REF].

The counting argument proceeds as follows. First, we focus on some subfile W f,S,T and we assume that the file W f,S is requested by some user k ∈ (S \ T ). Next, we count the number of demands (d π , f ) ∈ C for which k and right-most element included from T are at distance ℓ in π K . Then, we evaluate how many times the subfile appears in the index coding bounds associated to such demands. After that, noticing that ℓ ∈ [t ′ : α -1], we repeat the procedure for each value of ℓ. Finally, since the same procedure can be repeated for each k ∈ (S \ T ), we multiply the end result by

|S \ T | = (α -t ′ ).
Let us focus on the subfile W f,S,T for some f

∈ [F ], S ⊆ [K] with |S| = α, T ⊆ S and |T | = t ′ for some t ′ ∈ [0 : α]. For some user k ∈ (S \ T ) and for ℓ ∈ [t ′ : α -1], there is a total of a ℓ := t ′ !(α -1 -t ′ )!(K -α)! ℓ-1 t ′ -1 F K-1 demands (d π , f ) ∈ C such that the file W f,S
is requested by such user k ∈ (S \ T ) and there are exactly ℓ elements in π K between k and the right-most element included from T . Let C k,ℓ be the set of such demands. Considering how the acyclic set of vertices in [START_REF] Zhao | Vector coded caching multiplicatively boosts the throughput of realistic downlink systems[END_REF] is built, the subfile W f,S,T appears in the index coding bound induced by each (d π , f ) ∈ C k,ℓ whenever all the elements in T appear after k in u ∈ U (dπ,f ) . Since for each demand (d π , f ) ∈ C k,ℓ there are exactly ℓ elements in 5 Letting π ∈ H K be a circular permutation ensures that no d vector is repeated for any specific f vector.

π K separating k and the right-most element from T , we know from Lemma 2 that there are (K -ℓ) vectors u ∈ U (dπ,f ) where all the elements in T appear after k. Observing that ℓ ∈ [t ′ : α -1] and that such reasoning applies whenever the file W f,S is requested by any of the (α -t ′ ) users in S \ T , the specific subfile W f,S,T appears (α -t ′ ) α-1 ℓ=t ′ a ℓ (K -ℓ) times in [START_REF] Zhang | On the average rate for coded caching with heterogeneous user profiles[END_REF]. Since the same reasoning applies to any other subfile, the expression in ( 13) can be rewritten as

R ⋆ u,s ≥ 1 BK!F K (dπ,f )∈C u∈U (dπ ,f ) R(d π , f , u) (15)
= α t ′ =0 f (t ′ )x t ′ (16)
where f (t ′ ) and x t ′ are defined as

f (t ′ ) := N (α -t ′ ) F K K! α-1 ℓ=t ′ a ℓ (K -ℓ) (17)
0 ≤ x t ′ := S⊆[K]:|S|=α T ⊆S:|T |=t ′ f ∈[F ] |W f,S,T | N B . (18)
At this point, we seek to lower bound the minimum worstcase load R ⋆ u,s by lower bounding the solution to the following optimization problem

min x α t ′ =0 f (t ′ )x t ′ (19a) subject to α t ′ =0 x t ′ = 1 (19b) α t ′ =0 t ′ x t ′ ≤ KM N (19c)
where (19b) and (19c) correspond to the file-size constraint and the cumulative cache-size constraint, respectively.

3) Bounding the Solution to the Optimization Problem: The function f (t ′ ) can be simplified as

f (t ′ ) = α t ′ +1 + (K -α) α-1 t ′ α t ′ (20)
by means of the hockey-stick identity and after some algebraic manipulations. We encourage the reader to refer to [START_REF] Brunero | Unselfish coded caching can yield unbounded gains over symmetrically selfish caching[END_REF] for the technical passages. Then, x t ′ can be considered as a probability mass function and so the optimization problem in [START_REF] Arbabjolfaei | On the capacity region for index coding[END_REF] can be seen as the minimization of E[f (t ′ )]. Since we know from [START_REF] Brunero | Unselfish coded caching can yield unbounded gains over symmetrically selfish caching[END_REF]Lemma 3] that f (t ′ ) is convex and strictly decreasing for increasing t ′ , the sequence of inequalities E[f (t ′ )] ≥ f (E[t ′ ]) ≥ f (KM/N ) holds by Jensen's inequality and the memory-size constraint in (19c). Finally, for t := KM/N the converse bound is a piecewise linear curve with the corner points in [START_REF] Zhang | Coded caching under arbitrary popularity distributions[END_REF], concluding the proof.

B. A Detailed Example for the Converse Bound

Consider the symmetric (4, 3, 1) FDS structure which involves a file library L = {W 1,S : S ⊆ [START_REF] Tölli | Multi-antenna interference management for coded caching[END_REF], |S| = 3} consisting of C = K α = 4 3 = 4 classes of files. Since there is only F = 1 file per class, there is a total of N = F C = 4 files, so in this example we make no distinction between files and classes of files. For simplicity, we will here refer to file W 1,S directly as W S , which means that each file is entirely described by a 3-tuple S ⊆ [START_REF] Tölli | Multi-antenna interference management for coded caching[END_REF], and each demand instance is entirely defined by the d = (D 1 , . . . , D 4 ) vector only. The FDS of each user k ∈ [START_REF] Tölli | Multi-antenna interference management for coded caching[END_REF] is given by F k = {W S : S ⊆ [4], |S| = 3, k ∈ S} and it consists of F K-1 α-1 = 3 files. This example considers t ∈ [0 : 3], simply because having M = tN/K = 3 implies that the point (M, R) = (3, 0) is trivially achievable being each user able to preemptively cache the entirety of its FDS.

Assuming the most general uncoded and selfish cache placement, each file W S is split into a total of 2 α = 8 disjoint subfiles as If we identify again in the side information graph of the problem the acyclic set of vertices as in [START_REF] Zhao | Vector coded caching multiplicatively boosts the throughput of realistic downlink systems[END_REF], applying Lemma 1 yields the following lower bound

W S =
BR ⋆ u,s ≥ R(d, u) (22)
where now we define

R(d, u) := k∈[4] T ⊆(([4]\{u1,...,u k })∩Du k ) W Du k ,T . (23)
Recall that (22) holds for any demand d and any u = π 4 for some π ∈ S 4 .

2) Constructing the Optimization Problem and Bounding its Solution: As described in Section III-A, we let C be the set of distinct demands where we have a d π vector for each circular permutation π ∈ H 4 . The number of such permutations is (K -1)! = 6. For simplicity, we denote by π i the i-th circular permutation for i ∈ [START_REF] Zhang | Deep learning for wireless coded caching with unknown and time-variant content popularity[END_REF], where such circular permutations are given by and for each u ∈ U dπ i for a given d πi , we sum all such bounds and we obtain the expression given by i∈ [START_REF] Zhang | Deep learning for wireless coded caching with unknown and time-variant content popularity[END_REF]

π 4 1 = (1, 2, 3, 4) π 4 4 = (1, 3, 4, 2) (24) π 4 2 = (1, 2, 4, 3) π 4 5 = (1, 4, 2, 3) (25) π 4 3 = (1, 3, 2, 4) π 4 6 = (1, 4, 3, 2). (
u∈U dπ i BR ⋆ u,s ≥ i∈[6] u∈U dπ i R(d πi , u). (30)
We simplify (30) by counting how many times each subfile W S,T -for any S ⊆ [START_REF] Tölli | Multi-antenna interference management for coded caching[END_REF] with |S| = 3, T ⊆ S and |T | = t ′ with t ′ ∈ [0 : 3] -appears in (30). For example, let us focus on the subfile W 123,2 . First of all, we notice that such subfile may appear to the RHS of (22) whenever W 123 is requested by any user k ∈ (S \ T ) = {1, 3}. Assume that W 123 is requested by user 1, which means we consider the bounds with demands d π1 and d π3 . Denoting by ℓ the distance 6 between user 1 and user 2 in π 4 i for i ∈ {1, 3}, we notice that ℓ ∈ {1, 2}. We see that there is only π 4 1 for ℓ = 1, so W 123,2 appears (K -ℓ) = 3 times in the bounds with demand d π1 and permutations in U dπ 1 . Similarly, there is only π 4 3 for ℓ = 2, so W 123,2 appears (K -ℓ) = 2 times in the bounds with demand d π3 and permutations in U dπ 3 . Thus, summing over the possible values of ℓ, the subfile W 123,2 appears 3 + 2 = 5 times in the bounds with demands d π1 and d π3 , and their relative permutations of users. The same rationale follows for the bounds built with d π2 , d π6 and their relative permutations, i.e., the bounds where file W 123 is requested by user 3. Hence, the subfile W 123,2 appears in (30) a total of 2 × (3 + 2) = 10 times. The same holds for any other subfile cached at only one user and a similar counting argument can be made for arbitrary |T | = t ′ with t ′ ∈ [0 : 3], as described in Section III-A. Thus, we can formulate an optimization problem as in [START_REF] Arbabjolfaei | On the capacity region for index coding[END_REF], bounding its solution by means of Jensen's inequality and convexity of f (t ′ ). The resulting bound is a piecewise linear curve with corner points (M, R LB ) = (t, (3 -t)/(1 + t) + 1 -t/3) for each t ∈ [0 : 3].

IV. CONCLUSION

In this work, we investigated the effects that selfish caching can have on the optimal worst-case communication load in the coded caching framework. We proposed for a general FDS structure, which seeks to capture the degree of intersection between the interests of the different users, a novel informationtheoretic converse on the minimum worst-case communication load under uncoded and selfish prefetching. Such bound definitively resolves the question of whether selfish caching is generally beneficial or not. Indeed, since for the proposed symmetric FDS structure Corollary 1.1 reveals that any nonzero load brought about by symmetrically selfish caching is always (with the exception of the extreme points of t) strictly worse than the optimal load guaranteed in the unselfish scenario, we can claim that selfish coded caching can cause serious unbounded 7 performance deterioration in caching systems.

Example 1 (

 1 The Symmetric (4, 3, 2) FDS Structure). Consider the symmetric (K, α, F ) = (4, 3, 2) FDS structure. There areC = K α = 4classes 2 W 123 , W 124 , W 134 , W 234 and N = 8 files: W 1,123 and W 2,123 from class W 123 , then W 1,124 and W 2,124 from class W 124 , and so on. The K FDSs take the form

  {W S,T : T ⊆ S}, ∀S ⊆ [4] : |S| = 3 (21) where again W S,T is the subfile of W S cached by users in T . 1) Constructing the Index Coding Bound: For any given demand d = (D 1 , . . . , D 4 ) where the k-th user asks for a distinct file W D k for each k ∈ [4], we consider the index coding problem with K ′ = K = 4 users and N ′ = K2 α-1 = 16 messages, where each user k ∈ [4] has a desired message set M k = {W D k ,T : T ⊆ D k , k / ∈ T } and a side information set A k = {W S,T : S ⊆ [4], |S| = 3, T ⊆ S, k ∈ T }.

  For instance, it is U dπ 1 = {(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)}. Now, we create a bound as in (22) for each d πi with i ∈[START_REF] Zhang | Deep learning for wireless coded caching with unknown and time-variant content popularity[END_REF]

	26)
	None of the above permutations can be obtained as a rotation
	of any of the others. Hence, this ensures to have in C the
	following distinct demand vectors
	d π1 = (123, 234, 134, 124) d π4 = (134, 123, 234, 124) (27)

d π2 = (124, 234, 123, 134) d π5 = (124, 123, 134, 234) (28) d π3 = (123, 124, 234, 134) d π6 = (134, 124, 123, 234) (29) with U dπ i containing the 4 circular shifts of π 4 i .

This means that no vector (π(1), . . . , π(n)) with π ∈ Hn can be obtained as a rotation of (σ(1), . . . , σ(n)) for some σ ∈ Hn with σ ̸ = π.

For simplicity, we will omit braces and commas when indicating sets, such that for example W {1,2,3} may be written as W 123 .

Notice that we do not consider α ∈ {1, K} in the corollary. Indeed, when α = 1 the comparison is trivial, whereas for α = K the converse expression naturally matches that of unselfish coded caching.

When α = 1 the proof is trivial, since for such case we have only two integer points corresponding to t ∈ {0, 1}: when t = 0 the load is equal to K, and when t = 1 each user has enough memory to cache entirely its own FDS and the load is equal to 0. The case α = K corresponds to the standard MAN scenario already considered in[START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF].

We remind that such distance represents the number of elements which separate index 1 and index 2, including the latter.

This is proved in the longer version of this work[START_REF] Brunero | Unselfish coded caching can yield unbounded gains over symmetrically selfish caching[END_REF].