Search

This work identifies the fundamental limits of Multi-Access Coded Caching (MACC) where each user is connected to multiple caches in a manner that follows a generalized combinatorial topology. This topology stands out as it allows for unprecedented coding gains, even with very modest cache resources. First, we extend the setting and the scheme presented by Muralidhar et al. to a much more general topology that supports both a much denser range of users and the coexistence of users connected to different numbers of caches, all while maintaining the astounding coding gains, here proven to be exactly optimal, associated with the combinatorial topology. This is achieved, for this generalized topology, with a novel information-theoretic converse that we present here, which establishes, together with the scheme, the exact optimal performance under the assumption of uncoded placement. We subsequently consider different connectivity ensembles, including the very general scenario of the entire ensemble of all possible network connectivities/topologies, where any user can be connected to any subset of caches arbitrarily. For these settings, we develop novel converse bounds on the optimal performance averaged over the ensemble's different connectivities, considering the additional realistic scenario that the connectivity at delivery time is entirely unknown during cache placement. This novel analysis of topological ensembles leaves open the possibility that currently-unknown topologies may yield even higher gains, a hypothesis that is part of the bigger question of which network topology yields the most caching gains., 48 pages, 2 figures. Submitted to IEEE Transactions on Information Theory

In this paper, for each of six families of three-valued \begin{document}$ m $\end{document} -sequence correlation, we construct an infinite family of five-weight codes from trace codes over the ring \begin{document}$ R = \mathbb{F}_2+u\mathbb{F}_2 $\end{document} , where \begin{document}$ u^2 = 0. $\end{document} The trace codes have the algebraic structure of abelian codes. Their Lee weight distribution is computed by using character sums. Their support structure is determined. An application to secret sharing schemes is given. The parameters of the binary image are \begin{document}$ [2^{m+1}(2^m-1),4m,2^{m}(2^m-2^r)] $\end{document} for some explicit \begin{document}$ r. $\end{document}

International audience; The Goppa Code Distinguishing (GD) problem asks to distinguish efficiently a generator matrix of a Goppa code from a randomly drawn one. We revisit a distinguisher for alternant and Goppa codes through a new approach, namely by studying the dimension of square codes. We provide here a rigorous upper bound for the dimension of the square of the dual of an alternant or Goppa code, while the previous approach only provided algebraic explanations based on heuristics. Moreover, for Goppa codes, our proof extends to the non-binary case as well, thus providing an algebraic explanation for the distinguisher which was missing up to now. All the upper bounds are tight and match experimental evidence. Our work also introduces new algebraic results about products of trace codes in general and of dual of alternant and Goppa codes in particular, clarifying their square code structure. This might be of interest for cryptanalysis purposes.

Strongly walk regular graphs (SWRGs or $s$-SWRGs) form a natural generalization of strongly regular graphs (SRGs) where paths of length~2 are replaced by paths of length~$s$. They can be constructed as coset graphs of the duals of projective three-weight codes whose weights satisfy a certain equation. We provide classifications of the feasible parameters of these codes in the binary and ternary case for medium size code lengths. For the binary case, the divisibility of the weights of these codes is investigated and several general results are shown. It is known that an $s$-SWRG has at most 4 distinct eigenvalues $k > \theta_1 > \theta_2 > \theta_3$, and that the triple $(\theta_1, \theta_2, \theta_3)$ satisfies a certain homogeneous polynomial equation of degree $s - 2$ (Van Dam, Omidi, 2013). This equation defines a plane algebraic curve; we use methods from algorithmic arithmetic geometry to show that for $s = 5$ and $s = 7$, there are only the obvious solutions, and we conjecture this to remain true for all (odd) $s \ge 9$., Comment: 42 pages

The determination of the number of mixture components (the order) of a finite mixture model has been an enduring problem in statistical inference. We prove that the closed testing principle leads to a sequential testing procedure (STP) that allows for confidence statements to be made regarding the order of a finite mixture model. We construct finite sample tests, via data splitting and data swapping, for use in the STP, and we prove that such tests are consistent against fixed alternatives. Simulation studies and real data examples are used to demonstrate the performance of the finite sample tests-based STP, yielding practical recommendations of their use as confidence estimators in combination with point estimates such as the Akaike information or Bayesian information criteria. In addition, we demonstrate that a modification of the STP yields a method that consistently selects the order of a finite mixture model, in the asymptotic sense. Our STP is not only applicable for order selection of finite mixture models, but is also useful for making confidence statements regarding any sequence of nested models.

International audience; Dans cet article, nous dérivons des bornes de généralisation basées sur la théorie de l’information. Nous prouvons une borne dépendant de l’information mutuelle qui est plus générale que celle de Xu et Raginsky. Cependant, cette borne étant en espérance, nous apportons, à partir d’une technique de preuve simple, la possibilité de dériver une borne PAC-Bayésienne et désintégrée à partir de celle-ci.

International audience; In 2016, Google introduced the concept of Federated Learning (FL), enabling collaborative Machine Learning (ML). FL does not share local data but ML models, offering applications in diverse domains. This paper focuses on the application of FL to Intrusion Detection Systems (IDSs). There, common criteria to compare existing solutions are missing. In particular, this survey shows: (i) how FL-based IDSs are used in different domains; (ii) what differences exist between architectures; (iii) the state of the art of FL-based IDS. With a structured literature survey, this work identifies the relevant state of the art in FL-based intrusion detection from its creation in 2016 until 2021. It provides a reference architecture and a taxonomy to serve as guidelines to compare and design FLbased IDSs. Both are validated with the existing works. Finally, it identifies research directions for the application of FL to intrusion detection systems.

International audience; We prove that the covering radius of the Melas code M (m, q) of length n = q m − 1 over Fq is 2 if q > 3. We also prove that the covering radius of M (m, 3) is 3 is m ≥ 3, the covering radius of M (2, 3) is 4, and the covering radii of M (1, 2) and M (1, 3) are 1.

In the zero-error Slepian-Wolf source coding problem, the optimal rate is given by the complementary graph entropy $\overline{H}$ of the characteristic graph. It has no single-letter formula, except for perfect graphs, for the pentagon graph with uniform distribution $G_5$, and for their disjoint union. We consider two particular instances, where the characteristic graphs respectively write as an AND product $\wedge$, and as a disjoint union $\sqcup$. We derive a structural result that equates $\overline{H}(\wedge \: \cdot)$ and $\overline{H}(\sqcup \: \cdot)$ up to a multiplicative constant, which has two consequences. First, we prove that the cases where $\overline{H}(\wedge \:\cdot)$ and $\overline{H}(\sqcup \: \cdot)$ can be linearized coincide. Second, we determine $\overline{H}$ in cases where it was unknown: products of perfect graphs; and $G_5 \wedge G$ when $G$ is a perfect graph, using Tuncel et al.'s result for $\overline{H}(G_5 \sqcup G)$. The graphs in these cases are not perfect in general.

The effect of the relative entropy asymmetry is analyzed in the empirical risk minimization with relative entropy regularization (ERM-RER) problem. A novel regularization is introduced, coined Type-II regularization, that allows for solutions to the ERM-RER problem with a support that extends outside the support of the reference measure. The solution to the new ERM-RER Type-II problem is analytically characterized in terms of the Radon-Nikodym derivative of the reference measure with respect to the solution. The analysis of the solution unveils the following properties of relative entropy when it acts as a regularizer in the ERM-RER problem: i) relative entropy forces the support of the Type-II solution to collapse into the support of the reference measure, which introduces a strong inductive bias that dominates the evidence provided by the training data; ii) Type-II regularization is equivalent to classical relative entropy regularization with an appropriate transformation of the empirical risk function. Closed-form expressions of the expected empirical risk as a function of the regularization parameters are provided., To appear in the proceedings of the International Symposium on Information Theory 2023

The dependence on training data of the Gibbs algorithm (GA) is analytically characterized. By adopting the expected empirical risk as the performance metric, the sensitivity of the GA is obtained in closed form. In this case, sensitivity is the performance difference with respect to an arbitrary alternative algorithm. This description enables the development of explicit expressions involving the training errors and test errors of GAs trained with different datasets. Using these tools, dataset aggregation is studied and different figures of merit to evaluate the generalization capabilities of GAs are introduced. For particular sizes of such datasets and parameters of the GAs, a connection between Jeffrey's divergence, training and test errors is established., In Proc. IEEE International Symposium on Information Theory (ISIT), Taipei, Taiwan, Jun., 2023. arXiv admin note: text overlap with arXiv:2211.06617

International audience; Learning on entropy coded data has many benefits. First, it avoids decoding, but also it allows one to process compact data. However, this type of learning has been overlooked due to the chaos introduced by entropy coding functions. Indeed, convolution widely used in learning algorithm requires that the encoding function preserves the distance between pixel positions (spatial closeness), and the distance between pixel values (semantic closeness). Even if these two properties are not satisfied by entropy coding, we had shown previously that learning on entropy coded data is possible and that the accuracy depends on spatial and semantic closeness. In this paper, we quantify this dependence, and introduce a new metric, that measures the chaos in the data representation. This measure is easy to compute as it depends on the encoded data only. Moreover, this measures allows one to predict the accuracy of the learning algorithm, that process entropy coded data.

International audience; Recent advances in the fingerprinting of deep neural networks are able to detect specific instances of models, placed in a black-box interaction scheme. Inputs used by the fingerprinting protocols are specifically crafted for each precise model to be checked for. While efficient in such a scenario, this nevertheless results in a lack of guarantee after a mere modification of a model (e.g. finetuning, quantization of the parameters). In this paper we propose fingerprinting scheme (coined FBI) that are resilient to significant modifications of the models. These modifications are viewed and modeled as variants. We demonstrate that benign inputs, that are unmodified images, are sufficient material for efficient fingerprinting. We leverage an information-theoretic approach to achieve a success rate of 95.2%. It is experimentally validated over an unprecedented set of more than 1,000 neural networks, while demonstrating performance improvements over a state-of-the-art fingerprinting method.

The effect of the relative entropy asymmetry is analyzed in the empirical risk minimization with relative entropy regularization (ERM-RER) problem. A novel regularization is introduced, coined Type-II regularization, that allows for solutions to the ERM-RER problem with a support that extends outside the support of the reference measure. The solution to the new ERM- RER Type-II problem is analytically characterized in terms of the Radon-Nikodym derivative of the reference measure with respect to the solution. The analysis of the solution unveils the following properties of relative entropy when it acts as a regularizer in the ERM-RER problem: (a) relative entropy forces the support of the Type-II solution to collapse into the support of the reference measure, which introduces a strong inductive bias that dominates the evidence provided by the training data; (b) Type-II regularization is equivalent to classical relative entropy regularization with an appropriate transformation of the empirical risk function. Closed-form expressions of the expected empirical risk as a function of the regularization parameters are provided.; L’effet de l’asymétrie de l’entropie relative est analysé dans leproblème de la minimisation du risque empirique avec régularisation par entropierelative (MRE-RER). Une nouvelle régularisation est introduite, appeléerégularisation de type-II, qui permet la recherche des solutions au problème dela MRE-RER avec un support qui s’étend en dehors du support de la mesurede référence. La solution au nouveau problème de la MRE-RER Type-II estcaractérisée analytiquement en termes de la dérivée de Radon-Nikodym de lamesure de référence par rapport à la solution. L’analyse de la solution dévoilecertaines propriétés de l’entropie relative lorsqu’elle agit comme régularisateurdu problème de la MRE-RER : (a) l’entropie relative force le support de lasolution de type-II à s’étaler sur tout le support de la mesure de référence, cequi introduit un fort biais inductif qui domine l’évidence fournie par les donnéesd’entraînement ; (b) La régularisation de type-II est équivalente à la régularisationd’entropie relative classique avec une transformation appropriée de lafonction du risque empirique. Enfin, une expression sous forme explicite de lavaleur espérée du risque empirique en fonction des paramètres de régularisationest présentée.

In this report, 2 × 2 zero-sum games are studied under the following assumptions: (1) One of the players (the leader) commits to choose its actions by sampling a given probability measure (strategy); (2) The leader announces its action, which is observed by its opponent (the follower) through a binary channel; and (3) the follower chooses its strategy based on the knowledge of the leader’s strategy and the noisy observation of the leader’s action. Under these conditions, the equilibrium is shown to always exist. Interestingly, even subject to noise, observing the actions of the leader is shown to be either beneficial or immaterial for the follower. More specifically, the payoff at the equilibrium of this game is upper bounded by the payoff at the Stackelberg equilibrium (SE) in pure strategies; and lower bounded by the payoff at the Nash equilibrium, which is equivalent to the SE in mixed strategies. Finally, necessary and sufficient conditions for observing the payoff at equilibrium to be equal to its lower bound are presented. Sufficient conditions for the payoff at equilibrium to be equal to its upper bound are also presented.; Dans ce rapport, les jeux à somme nulle 2 × 2 sont étudiés sous les hypothèses suivantes : (1) L’un des joueurs (le meneur) s’engage à choisir ses actions en échantillonnant une mesure de probabilité donnée (stratégie) ; (2) Le meneur annonce son action, qui est observée par son adversaire (le suiveur) à travers un canal binaire ; et (3) le suiveur choisit sa stratégie en fonction de la connaissance de la stratégie du meneur et de l’observation bruitée de l’action du meneur. Dans ces conditions, on montre que l’équilibre existe toujours. Fait intéressant, même sujette au bruit, l’observation des actions du leader s’avère soit bénéfique, soit immatérielle pour le suiveur. Plus précisément, la récompense à l’équilibre de ce jeu est majorée par la récompense à l’équilibre de Stackelberg (SE) en stratégies pures, et minorée par la récompense à l’équilibre de Nash, qui équivaut au SE en stratégies mixtes. Enfin, les conditions nécessaires et suffisantes pour observer que la récompense à l’équilibre est égale à sa borne inférieure sont présentées. Les conditions suffisantes pour observer que la récompense à l’équilibre est égale à sa borne supérieure sont aussi présentées.

International audience; This work elevates coded caching networks from their purely information-theoretic framework to a stochastic setting, by exploring the effect of random user activity and by exploiting correlations in the activity patterns of different users. In particular, the work studies the K-user cache-aided broadcast channel with a limited number of cache states (i.e., the content stored at the cache of a certain user), and explores the effect of cache state association strategies in the presence of arbitrary user activity levels; a combination that strikes at the very core of the coded caching problem and its crippling subpacketization bottleneck. We first present a statistical analysis of the average worst-case delay performance of such subpacketization-constrained (state-constrained) coded caching networks, and provide computationally efficient performance bounds as well as scaling laws for any arbitrary probability distribution of the user-activity levels. The achieved performance is a result of a novel user-to-cache state association algorithm that leverages the knowledge of probabilistic user-activity levels. We then follow a data-driven approach that exploits the prior history on user-activity levels and correlations, in order to predict interference patterns, and thus better design the caching algorithm. This optimized strategy is based on the principle that users that overlap more, interfere more, and thus have higher priority to secure complementary cache states. This strategy is proven here to be within a small constant factor from the optimal. Finally, the above analysis is validated numerically using synthetic data following the Pareto principle. To the best of our understanding, this is the first work that seeks to exploit user-activity levels and correlations, in order to map future interference and design optimized coded caching algorithms that better handle this interference.

Résumé Algebraic error-correcting codes respond to numerous needs that emerge from the world of digital communications and information. The mathematical structure of these families of codes allows the design of efficient encoding and decoding algorithms, thus enabling a variety of applications in modern technologies. In this manuscript, we delve into two of these aspects. First, we tackle the decoding problem for Reed-Solomon codes. We propose a new strategy that consists of solving a polynomial system, whose equations are connected to the power decoding algorithm, by using Gröbner bases techniques. We show that for some parameters our approach allows to reach and exceed Johnson's radius. We then move to some topics related to code-based cryptography. The oldest public key encryption scheme relying on codes was proposed in 1978 by McEliece. After more than four decades, McEliece's scheme is still secure and even quantum computers do not represent a threat. We analyze the algebraic structure and the security of subfield subcodes of Reed-Solomon codes, namely alternant and Goppa codes. Among others, McEliece's scheme is built upon binary Goppa codes. We investigate an algebraic method that allows to distinguish alternant and Goppa codes from random ones, provided that their rate is high enough. This study brings us to develop a polynomial-time attack on high-rate alternant codes. Again, we exploit Gröbner bases to solve a polynomial system that models the key-recovery problem. Finally, we give a procedure to enhance in some cases the range of distinguishable parameters.; Les codes correcteurs d'erreurs algébriques répondent à de nombreux besoins du monde des communications et de l'information. La structure mathématique de ces familles de codes permet la conception d'algorithmes de codage et de décodage efficaces, permettant ainsi une variété d'applications technologiques. Dans ce manuscrit, nous nous intéressons à deux de ces aspects. Premièrement, nous abordons le problème du décodage des codes de Reed-Solomon. Nous proposons une nouvelle stratégie qui consiste à résoudre un système polynomial, dont les équations sont liées au ``power decoding'', en utilisant des techniques de bases de Gröbner. Nous montrons que pour certains paramètres notre approche permet d'atteindre et de dépasser le rayon de Johnson. Nous abordons ensuite la cryptographie à base de codes. Le plus ancien schéma de chiffrement à clé publique reposant sur des codes a été proposé en 1978 par McEliece. Après plus de quarante ans, le schéma de McEliece est toujours sûr et ce même vis à vis des ordinateurs quantiques. Nous analysons la structure algébrique et la sécurité des codes de Goppa et d'une famille plus large, les codes alternants. Le schéma de McEliece est construit à partir de codes de Goppa binaires. Nous étudions une méthode qui permet de distinguer ces derniers de codes aléatoires, pour peu que leur rendement soit suffisamment élevé. Nous développons aussi une attaque en temps polynomial sur les codes alternants à rendement élevé. Là encore, nous exploitons les bases de Gröbner pour résoudre un système qui modélise le problème de retrouver la clé secrète. Enfin, nous donnons une procédure pour améliorer dans certains cas la gamme des paramètres distinguables.

This paper deals with time and frequency synchronization in LoRa system based on the preamble symbols. A thorough analysis of the maximum likelihood (ML) estimator of the delay (time offset) and the frequency offset shows that the resulting cost function is not concave. As a consequence the a priori solution to the maximization problem consists in exhaustively searching over all the possible values of both the delay and the frequency offset. Furthermore, it is shown that these parameters are intertwined and therefore they must be jointly estimated, leading to an extremely complex solution. Alternatively, we show that it is possible to recover the concavity of the cost function, from which we suggest a low-complexity synchronization algorithm, whose steps are described in detail. Simulations results show that the suggested method reaches the same performance as the ML exhaustive search, while the complexity is drastically reduced, allowing for a real-time implementation of a LoRa receiver.

This paper examines the average age minimization problem where only a fraction of the network users can transmit simultaneously over unreliable channels. Finding the optimal scheduling scheme, in this case, is known to be challenging. Accordingly, the Whittle’s index policy was proposed in the literature as a low-complexity heuristic to the problem. Although simple to implement, characterizing this policy’s performance is recognized to be a notoriously tricky task. In the sequel, we provide a new mathematical approach to establish its optimality in the many-users regime for specific network settings. Contrary to previous works in the literature that use restrictive mathematical assumptions, which can be challenging to verify, our novel approach is based on intricate techniques and it is free of any strong mathematical assumptions. These findings showcase that the Whittle’s index policy has analytically provable asymptotic optimality for the AoI minimization problem. Finally, we lay out numerical results that corroborate our theoretical findings and demonstrate the policy’s notable performance in the many-users regime.

In recent years, Empirical Bayesian (EB) inference has become an attractive approach for estimation in parametric models arising in a variety of real-life problems, especially in complex and high-dimensional scientific applications. However, compared to the relative abundance of available general methods for computing point estimators in the EB framework, the construction of confidence sets and hypothesis tests with good theoretical properties remains difficult and problem specific. Motivated by the universal inference framework of Wasserman et al. [2020], we propose a general and universal method, based on holdout likelihood ratios, and utilizing the hierarchical structure of the specified Bayesian model for constructing confidence sets and hypothesis tests that are finite sample valid. We illustrate our method through a range of numerical studies and real data applications, which demonstrate that the approach is able to generate useful and meaningful inferential statements in the relevant contexts.

International audience; We here continue the exploration of vector coded caching and its powerful effect on the performance of multiuser multiple-input multiple-output (MU-MIMO) systems. In particular, this paper investigates the impact that vector coded caching under various practical considerations, which include channel state information acquisition costs, multi-antenna receivers, variable pathloss, as well as max-min fairness where the minimum transmission rate among the simultaneously served users is maximized via power allocation. We here focus on the widely adopted zero-forcing precoder, and proceed to show the large multiplicative boost brought about by vector coded caching over the optimized cacheless counterpart. To do so, we here provide lower and upper bounds on the overall throughput as well as on the effective gain (i.e., on the rate improvement over the optimized cacheless counterpart), again in the presence of the aforementioned practical aspects. Finally various numerical results demonstrate the tightness of the derived upper and lower bounds, as well as nicely illustrate the notable gains.

Today, a massive shift is ongoing in telecommunication networks with the emergence of softwarization and cloudification. Among the technologies which are assisting these shifts, one of them is NFV (Network Function Virtualization). NFV is the network architecture that decouples network functions from hardware devices (middleboxes) with the help of a virtual component known as VNF (Virtual Network Function). VNF has shifted the network technological paradigm. Before: Network Function was performed by physical equipment, and service providers acquired its property for the lifetime of the relying hardware (instead counted in years). Today, Network functions are software that service providers develop or acquire purchasing licenses. A license defines software's Right to Use (RTU). Therefore, if licensing in NFV is not appropriately managed, service providers might (1) be exposed to counterfeiting and risk heavy financial penalties due to non-compliance; (2) might overbuy licenses to cover poorly estimated usages. Thus, mastering network function license through implementing Software Asset Management and FinOps (Finance and DevOps) is essential to control costs. In this research, our primary problem is to minimize the TCO (Total Cost of Ownership) of software cost (VNF), providing Quality of Services (QoS) to a specific amount of users. Software costs include various costs, from development to maintenance, integration to release management, and professional services. Our research focuses on proprietary software (developed by a publisher and sold via a paid license). We considered that TCO consists of the software license cost, the resources necessary to execute and operate SW, and the energy consumed by this execution. In this research, first, we have identified the need for a standardized VNF licensing model, which is highly dependent on the VNF provider's creativity; This lack of standards places CSPs (Communication Service Providers) at risk of having to delegate the management of rights to suppliers. Hence, we proposed a licensing model based on the metrics, which help to quantify the usage of the VNF. After estimating the license of VNF, we estimated the license cost. Afterward, we presented several ways to minimize the license cost depending upon the different use cases, which depend on the user's scenario and needs. Then after, with the help of industrial knowledge, we found that reducing resource consumption to minimize the TCO providing QoS affects the deployment of the VNF directly or indirectly, which impacts the licensing. Thus, the licenses and resources are interdependent. We used these costs to construct the software's total cost. After that, we proposed several ways to reduce the software's total cost by fulfilling the client's requirements. Then after, we considered the energy and its associated cost of VNF. The energy consumption of the VNF is dependent on resource consumption, and resources usages impact the license. Thus, we can see that these three costs are interdependent: license, resources, and energy cost of VNF. Hence, we consider these costs and constructed TCO. Minimizing TCO fulfilling the client's requirements is challenging since it is a multi-parameter. Therefore, we proposed several heuristical algorithms based on resource sharing and consolidation to reduce the TCO depending on the license, resource preference, and the client's scenarios.; Aujourd’hui, un changement massif est en cours dans les réseaux de télécommunication avec l’émergence de la softwarisation et de la cloudification. Parmi les technologies qui accompagnent ces mutations, l’une d’elles est la NFV (Network Function Virtualization). NFV est l’architecture réseau qui découple les fonctions réseau des périphériques matériels (middleboxes) à l’aide d’un composant virtuel appelé VNF (Virtual Network Function). VNF a changé le paradigme technologique des réseaux. Avant : la fonction de réseau était assurée par un équipement physique et les fournisseurs de services acquéraient sa propriété pour la durée de vie du matériel de confiance (au lieu de compter en années). Aujourd’hui, les fonctions réseau sont des logiciels que les fournisseurs de services développent ou acquièrent en achetant des licences. Une licence définit le droit d’utilisation (RTU) du logiciel. Par conséquent, si l’octroi de licences dans la NFV n’est pas géré de manière appropriée, les fournisseurs de services pourraient (1) être exposés à la contrefaçon et risquer de lourdes sanctions financières en cas de non-conformité ; (2) pourrait suracheter des licences pour couvrir des usages mal estimés. Ainsi, la maîtrise de la licence de fonction réseau via la mise en place du Software Asset Management et du FinOps (Finance et DevOps) est indispensable pour maîtriser les coûts. Dans cette recherche, notre problème principal est de minimiser le TCO (Total Cost of Ownership) du coût du logiciel (VNF), en fournissant une Qualité de Services (QoS) à un nombre spécifique d’utilisateurs. Les coûts des logiciels comprennent divers coûts, du développement à la maintenance, de l’intégration à la gestion des versions et des services professionnels. Nos recherches portent sur les logiciels propriétaires (développés par un éditeur et vendus via une licence payante). Nous avons considéré que le TCO se compose du coût de la licence du logiciel, des ressources nécessaires pour exécuter et faire fonctionner le SW, et de l’énergie consommée par cette exécution. Dans cette recherche, premièrement, nous avons identifié le besoin d’un modèle de licence VNF standardisé, qui dépend fortement de la créativité du fournisseur VNF ; Cette absence de normes expose les CSP (Communication Service Providers) au risque de devoir déléguer la gestion des droits aux fournisseurs. Par conséquent, nous avons proposé un modèle de licence basé sur les métriques, qui aide à x quantifier l’utilisation du VNF. Après avoir estimé la licence de VNF, nous avons estimé le coût de la licence. Ensuite, nous avons présenté plusieurs façons de minimiser le coût de la licence en fonction des différents cas d’utilisation, qui dépendent du scénario et des besoins de l’utilisateur. Puis après, avec l’aide des connaissances industrielles, nous avons constaté que la réduction de la consommation de ressources pour minimiser le TCO fournissant la QoS affecte le déploiement de la VNF directement ou indirectement, ce qui impacte l’octroi de licences. Ainsi, les licences et les ressources sont interdépendantes. Nous avons utilisé ces coûts pour construire le coût total du logiciel. Après cela, nous avons proposé plusieurs façons de réduire le coût total du logiciel en répondant aux exigences du client. Puis après, nous avons considéré l’énergie et son coût associé de VNF. La consommation énergétique du VNF est dépendante de la consommation des ressources, et les usages des ressources impactent la licence. Ainsi, on voit que ces trois coûts sont interdépendants : licence, ressources et coût énergétique de VNF. Par conséquent, nous considérons ces coûts et le TCO construit. Minimiser le coût total de possession en répondant aux exigences du client est un défi car il s’agit d’un multi-paramètres.

International audience; We introduce a new approach to improve and adapt transformers for multi-label text classification. Dependencies between labels are an important factor in the multi-label context. Our proposed strategies take advantage of co-occurrences between labels. Our first approach consists in updating the final activation of each label by a weighted sum of all activations by these occurrence probabilities. The second proposed method consists in including the activations of all labels in the prediction. This is done using an approach similar to the 'self-attention' mechanism. As the most known multi-label datasets tend to have a small cardinality, we propose a new dataset, called 'arXiv-ACM', comprised of scientific abstracts from arXiv, tagged with their ACM keywords. We show that our approaches contribute to a performance gain, establishing a new state of the art for the studied datasets.; Nous présentons une nouvelle approche pour améliorer et adapter les transformeurs pour la classification multi-labels de textes. Les dépendances entre les labels sont un facteur important dans le contexte multi-labels. Les stratégies que nous proposons tirent profit des co-occurrences entre labels. Notre première approche consiste à mettre à jour l'activation de chaque label par une somme pondérée de toutes les activations par les probabilités d'occurrence. La deuxième méthode proposée consiste à inclure les activations de tous les labels dans la prédiction, en utilisant une approche similaire au mécanisme de 'selfattention'. Les jeux de données multi-labels les plus connus ont tendance à avoir une faible cardinalité, nous proposons un nouveau jeu de données, appelé 'arXiv-ACM', composé de résumés scientifiques d'arXiv, étiquetés avec leurs mots-clés ACM. Nous montrons que nos approches contribuent à un gain de performance, établissant un nouvel état de l'art pour les jeux de données étudiés.

Blockchain is a method of recording information that makes it not feasible for the system to be replaced, attacked, or manipulated. A blockchain is equipped with a notebook that copies and processes the various procedures across the network of computers participating in the blockchain. Digital signature algorithm is one of the cryptographic protocols used by the blockchain. In this work, we introduce a new digital signature scheme based on error correcting codes. In the scheme constructed on a [n, k, d]− code over 𝔽q, which is d ≥ 2t + 1, and the size of the signature length is n − k. The signature verification is based on the bounded distance decoding of the code. Since the verification space is 𝔽qn, the proposed scheme has an improved performance in terms of working in a wider space.

International audience; The main motivation of this work is to study and obtain some reversible and DNA codesof length n with better parameters. Here, we first investigate the structure of cyclic and skew cycliccodes over the chain ring R : = F 4 [ v ] / ⟨ v 3 ⟩ . We show an association between the codons and theelements of R using a Gray map. Under this Gray map, we study reversible and DNA codes of lengthn. Finally, several new DNA codes are obtained that have improved parameters than previouslyknown codes. We also determine the Hamming and the Edit distances of these codes.

A necessary condition for a Z 4-code to be a three-weight code for the Lee weight is given. Two special constructions of three-weight codes over Z 4 are derived. The coset graphs of their duals are shown to be strongly 3-walk-regular, a generalization of strongly regular graphs.

Channel charting is a recently proposed framework that applies dimensionality reduction to channel state information (CSI) in wireless systems with the goal of associating a pseudo-position to each mobile user in a low-dimensional space: the channel chart. Channel charting summarizes the entire CSI dataset in a self-supervised manner, which opens up a range of applications that are tied to user location. In this article, we introduce the theoretical underpinnings of channel charting and present an overview of recent algorithmic developments and experimental results obtained in the field. We furthermore discuss concrete application examples of channel charting to network- and user-related applications, and we provide a perspective on future developments and challenges as well as the role of channel charting in next-generation wireless networks., Accepted for publication in the IEEE Communication Magazine

We consider the problem of computing a Gaussian approximation to the posterior distribution of a parameter given a large number N of observations and a Gaussian prior, when the dimension of the parameter d is also large. To address this problem we build on a recently introduced recursive algorithm for variational Gaussian approximation of the posterior, called recursive variational Gaussian approximation (RVGA), which is a single pass algorithm, free of parameter tuning. In this paper, we consider the case where the parameter dimension d is high, and we propose a novel version of RVGA that scales linearly in the dimension d (as well as in the number of observations N), and which only requires linear storage capacity in d. This is afforded by the use of a novel recursive expectation maximization (EM) algorithm applied for factor analysis introduced herein, to approximate at each step the covariance matrix of the Gaussian distribution conveying the uncertainty in the parameter. The approach is successfully illustrated on the problems of high dimensional least-squares and logistic regression, and generalized to a large class of nonlinear models., Comment: Statistics and Computing, In press

IEEE 802.11p standard defines wireless technology protocols that enable vehicular transportation and manage traffic efficiency. A major challenge in the development of this technology is ensuring communication reliability in highly dynamic vehicular environments, where the wireless communication channels are doubly selective, thus making channel estimation and tracking a relevant problem to investigate. In this paper, a novel deep learning (DL)-based weighted interpolation estimator is proposed to accurately estimate vehicular channels especially in high mobility scenarios. The proposed estimator is based on modifying the pilot allocation of the IEEE 802.11p standard so that more transmission data rates are achieved. Extensive numerical experiments demonstrate that the developed estimator significantly outperforms the recently proposed DL-based frame-by-frame estimators in different vehicular scenarios, while substantially reducing the overall computational complexity., 16 pages

The collection of animal position data via GPS tracking devices has increased in quality and usage in recent years. Animal position and movement, although measured discretely, follows the same principles of kinematic motion, and as such, the process is inherently continuous and differentiable. I demonstrate the functionality and visual elegance of smoothing spline models. I discuss the challenges and benefits of implementing such an approach, and I provide an analysis of movement and social interaction of seven jaguars inhabiting the Taiamã Ecological Station, Pantanal, Brazil, a region with the highest known density of jaguars. In the analysis, I derive measures for pairwise distance, cooccurrence, and spatiotemporal association between jaguars, borrowing ideas from density estimation and information theory. These measures are feasible as a result of spline model estimation, and they provide a critical tool for a deeper investigation of cooccurrence duration, frequency, and localized spatio‐temporal relationships between animals. In this work, I characterize a variety of interactive relationships between pairs of jaguars, and I particularly emphasize the relationships in movement of two male–female and two male–male jaguar pairs exhibiting highly associative relationships., I propose the use of smoothing spline models to explore animal movement and social interaction. I propose temporal‐state density estimation and localized mutual information measures to characterize behavior and strength of association between jaguars on a refined and unified time grid. I provide further characterization of time‐dependent male–male and female–male relationships in this region, an important step in determining conservation policy for an endangered neotropical predator.

Compressed sensing (CS) ensures the recovery of sparse vectors from a number of randomized measurements proportional to their sparsity. The initial theory considers discretized domains, and the randomness makes the physical positions of the grid nodes irrelevant. Most imaging devices, however, operate over some continuous physical domain, and it makes sense to consider Dirac masses with arbitrary positions. In this article, we consider such a continuous setup and analyze the performance of the BLASSO algorithm, which is the continuous extension of the celebrated LASSO $$\ell ^1$$ regularization method. This approach is appealing from a numerical perspective because it avoids to discretize the domain of interest. Previous works considered translation-invariant measurements, such as randomized Fourier coefficients, in which it makes clear that the discrete theory should be extended by imposing a minimum distance separation constraint (often called “Rayleigh limit”) between the Diracs. These prior works, however, rule out many domains and sensing operators of interest, which are not translation invariant. This includes, for instance, Laplace measurements over the positive reals and Gaussian mixture models over the mean-covariance space. Our theoretical advances crucially rely on the introduction of a canonical metric associated with the measurement operator, which is the so-called Fisher geodesic distance. In the case of Fourier measurements, one recovers the Euclidean metric, but this metric can cope with arbitrary (possibly non-translation invariant) domains. Furthermore, it is naturally invariant under joint reparameterization of both the sensing operator and the Dirac locations. Our second and main contribution shows that if the Fisher distance between spikes is larger than a Rayleigh separation constant, then the BLASSO recovers in a stable way a stream of Diracs, provided that the number of measurements is proportional (up to log factors) to the number of Diracs. We measure the stability using an optimal transport distance constructed on top of the Fisher geodesic distance. Our result is (up to log factor) sharp and does not require any randomness assumption on the amplitudes of the underlying measure. Our proof technique relies on an infinite-dimensional extension of the so-called golfing scheme which operates over the space of measures and is of general interest.

It is well known that the capacity region of an average transmit power constrained Gaussian Broadcast Channel (GBC) with independent noise realizations at the receivers is enlarged by the presence of causal noiseless feedback. Capacity region enlargement is also known to be possible by using only passive noisy feedback, when the GBC has identical noise variances at the receivers. The last fact remains true even when the feedback noise variance is very high, and available only from one of the receivers. While such capacity enlargements are feasible for several other feedback models in the Gaussian BC setting, it is also known that feedback does not change the capacity region for physically degraded broadcast channels. In this paper, we consider a two user GBC with independent noise realizations at the receivers, where the feedback links from the receivers are corrupted by independent additive Gaussian noise processes. We investigate the set of four noise variances, two forward and two feedback, for which no capacity enlargement is possible. A sharp characterization of this region is derived, i.e., any quadruple outside the presented region will lead to a capacity enlargement, whereas quadruples inside will leave the capacity region unchanged. Our results lead to the conclusion that when the forward noise variances are different, too noisy a feedback from one of the receivers alone is not always beneficial for enlarging the capacity region, be it from the stronger user or the weaker one, in sharp contrast to the case of equal forward noise variances., 23 single column pages, 4 Figures

The vector-valued extension of the famous Witsenhausen counterexample setup is studied where the encoder, i.e. the first decision maker, non-causally knows and encodes the i.i.d. state sequence and the decoder, i.e. the second decision maker, causally estimates the interim state. The coding scheme is transferred from the finite alphabet coordination problem for which it is proved to be optimal. The extension to the Gaussian setup is based on a nonstandard weak typicality approach and requires a careful average estimation error analysis since the interim state is estimated by the decoder. We provide a single-letter expression that characterizes the optimal trade-off between the Witsenhausen power cost and estimation cost. The two auxiliary random variables improve the communication with the decoder, while performing the dual role of the channel input, which also controls the state of the system. Interestingly, we show that a pair of discrete and continuous auxiliary random variables, outperforms both Witsenhausen two point strategy and the best affine policies. The optimal choice of random variables remains unknown.

Algebraic linear codes J/I ⊂ Fq[X1,. .. Xm]/I that are finite dimension quotients of multivariate polynomial rings, have been studied intensively; in particular m-dimensional cyclic codes where the ideal I is (X n 1 1 − 1,. .. , X nm m − 1). Recently this notion has been extended to two dimensional skew cyclic codes using multivariate skew polynomial rings over fields [12, 16, 18] and even over rings [15]. In this paper we use a Gröbner basis approach in order to generalize algebraic linear codes and m-dimensional cyclic codes to the skew polynomial rings setting. The approach encompass all previous results on m-dimensional (consta-)cyclic codes and allows for many generalizations.

Over the past few decades, the adoption of e-learning has evolved rapidly and its use has been pushedeven further with the COVID-19 pandemic. The objective of this learning mode is to guarantee the continuity of the learning process. However, the online learning is facing several challenges, and the most widespread is the high failure rates among learners. This issue is due to many reasons such asthe heterogeneity of the learners and the diversity of their learning behaviors, their total autonomy, the lack and/or the inefficiency of the pedagogical provided follow-up. Therefore, teachers need a system based on analytical and intelligent methods allowing them an accurate and early prediction of at-risk of failure learners. This solution is commonly adopted in the state of the art. However, the work carried out does not respond to some particularities of the learning process (the continuity and evolution of learning, the diversity of learners and their total autonomy) and to some teachers expectations such as the alert generation. This thesis belongs to the field of learning analytics and uses the numeric traces of online learnersto design a predictive system (Early Warning Systems (EWS)) dedicated to teachers in online establishments. The objective of this EWS is to identify learners at risk as soon as possible in order to alert teachers about them. In order to achieve this objective, we have dealt with several sub-problems which have allowed us to elaborate four scientific contributions. We start by proposing an in-depth methodology based on the Machine Learning (ML) steps and that allows the identification of four learning indicators among : performance, engagement, reactivity and regularity. This methodology also highlights the importance of temporal data for improving prediction performance. In addition, this methodology allowed to define the model with the best ability to identify at-risk learners. The 2nd contribution consists in proposing a temporal evaluation of the EWS using temporal metrics which measure the precocity of the predictions and the stability of the system. From these two metrics,we study the trade-offs that exist between ML precision metrics and temporal metrics. Online learners are characterized by the diversity of their learning behaviors. Thus, an EWS should respond to this diversity by ensuring an equitable functioning with the different learners profiles. We propose an evaluation methodology based on the identification of learner profiles and that uses a wide spectrum of temporal and precision metrics. By using an EWS, teachers expect an alert generation. For this reason, we design an algorithm which, based on the results of the prediction, the temporal metrics and the notion of alert rules, proposes an automatic method for alert generation. This algorithm targets mainly at-risk learners. The context of this thesis is the French National Center for Distance Education (CNED). In particular, we use the numeric traces of k-12 learners enrolled during the 2017-2018 and 2018-2019 school years.; Pendant les dernières décennies, l'adoption de l'apprentissage en ligne a rapidement évolué et son utilisation a été encore plus poussée avec la pandémie de la COVID-19. L'objectif de ce mode d'enseignement est de garantir la continuité du processus d'apprentissage. Cependant, ce mode d'apprentissage connaît plusieurs défis, dont le plus répandu est les taux élevés d'échec. Ce problème est dû à de nombreuses raisons comme l'hétérogénéité des apprenants et la diversité de leurs comportements d'apprentissage, leur totale autonomie, le manque et/ou l'inefficacité du suivi pédagogique fourni. Par conséquent, les enseignants ont besoin d'un système basée sur des méthodes analytiques et intelligentes leur permettant une prédiction précise et au plus tôt des apprenants à risque d'échec. Cette solution est communément adaptée dans l'état de l'art. Cependant, les travaux réalisés ne répondent pas à certaines particularités de l'apprentissage (la continuité et l'évolution de l'apprentissage, la diversité des apprenants et leur totale autonomie) et certaines attentes des enseignants comme la génération d'alerte. Cette thèse s'inscrit dans le domaine de l'analyse de l'apprentissage et exploite les traces numériques des apprenants en ligne pour concevoir un système prédictif (Early Warning Systems (EWS)) dédié aux enseignants des établissements en ligne. L'objectif de ce EWS est d'identifier au plus tôt les apprenants à risque pour alerter les enseignants de ces derniers. Afin d'atteindre cet objectif, nous avons traité plusieurs sous-problématiques qui ont permis l'élaboration de quatre contributions scientifiques. Nous commençons par proposer une méthodologie en profondeur qui repose sur les étapes de l'apprentissage automatique (ML) et qui permet l'identification de quatre indicateurs d'apprentissage parmi : la performance, l'engagement, la réactivité et la régularité. Cette méthodologie met aussi en valeur l'importance des données temporelles pour l'amélioration des performances de prédiction. De plus, cette méthodologie a permis de définir le modèle avec la meilleure capacité à identifier les apprenants à risque. La 2ème contribution consiste à proposer une évaluation temporelle des EWS à l'aide des métriques temporelles qui mesurent la précocité des prédictions et la stabilité des systèmes. À partir de ces deux métriques, nous étudions les compromis qui existent entre les métriques de précision de ML et les métriques temporelles. Les apprenants en ligne se caractérisent par la diversité de comportements d'apprentissage. Ainsi, un EWS doit répondre à cette diversité en assurant un fonctionnement équitable entre les différents profils d'apprenants. Nous proposons une méthodologie d'évaluation qui se base sur l'identification des profils d'apprenants et utilise un large spectre de métriques temporelles et de précision. En utilisant un EWS, les enseignants s'attendent à une génération d'alerte. C'est pour cette raison,nous concevons un algorithme qui s'appuie sur les résultats de prédiction, les métriques temporelles et la notion des règles d'alerte pour proposer une méthode automatique de génération d'alerte. Le contexte applicatif de cette thèse est le Centre National d'Enseignement à Distance (CNED). Nous exploitons les traces numériques d'une population de collégiens inscrits en classe 3ème pendant les années scolaires 2017-2018 et 2018-2019.

This HDR manuscript presents recent Information-Theoretic tools that bring new insights into Game Theoretical problems, such as the coordination of players’ actions and the processing of strategic information. Although Information Theory and Game Theory have distinct fields of application, these two theories rely on similar mathematical tools. Such problems arise for the design of autonomous devices and for the study of the behavior of rational agents. New generations of communication networks involve devices that take decisions with greater autonomy. These machines observe their environment, interact, cooperate with other machines or with humans, adapt dynamically to their environment and to the topology of the network. The lossy source coding theorem of Shannon (1959) is the cornerstone of our study. Given a communication capacity constraint, this theorem characterizes the optimal coding scheme to compress an information source. The coding performances are evaluated via a fidelity criterion which we interpret as a cost function to be minimized. We revisit this coding problem by adopting a Game-Theoretical point of view, in which each player optimizes his own cost function which depends on the actions of other players. First, we investigate the capacity of an encoder and a decoder to coordinate their actions with the symbols of an information source. For this purpose, the action sequence of the encoder encapsulates a degraded version of the source symbols, which serves to coordinate the future actions of the decoder. We characterize the solutions of several instances of the coordination problem in Chap. IV, and in Chap. V, we extend these results in several directions, i.e. for channel state leakage problems, for decentralized control problems and for strong coordination problems. The strategic nature of the information transmission is studied in Chap. VI when the communication is passed through a noisy channel. We consider that the encoder commits to implementing a signalling strategy before it observes the source symbols, as in the Bayesian persuasion game. As perspectives, we will study the impact of communication constraints on the transmission of strategic information in mechanism design problems, as in Jackson and Sonnenschein (2007), and in cheap talk games, see Crawford and Sobel (1982). Another direction of research consists in deepening optimization problems that arise in strategic coding, by using tools from Graph Theory and Convex Optimization. We believe that these results will also bring a new point of view on open problems in repeated games with imperfect observation and incomplete information. The goal is to build a theory that encompasses the standard coding results in Information Theory, and the results for the sender-receiver games., Ce manuscrit d’HDR présente des résultats récents de Théorie de l’Information qui apportent un éclairage nouveau sur des problèmes de Théorie des Jeux, tels que la coordination des actions des joueurs ou le traitement de l’information stratégique. Bien que la Théorie de l’Information et la Théorie des Jeux aient des champs d’application distincts, ces deux théories s’appuient sur des outils mathématiques similaires. Les problèmes de coordination et d’information stratégique se posent pour la conception de réseaux d’appareils autonomes et pour l’étude du comportement d’agents rationnels. Les nouvelles générations de réseaux de communication intègrent des appareils qui prennent des décisions avec une plus grande autonomie. Ces machines observent leur environnement, interagissent, coopèrent avec d’autres machines ou avec des humains, s’adaptent dynamiquement à leur environnement et à la topologie du réseau. Le théorème de codage de source avec perte de Shannon (1959) est la pierre angulaire de notre étude. Étant donnée une contrainte de capacité de communication, ce théorème caractérise le schéma de codage optimal pour compresser une source d’information. Les performances du codage sont évaluées via un critère de fidélité que nous interprétons comme une fonction de coût à minimiser. Nous revisitons ce problème de codage en adoptant le point de vue de la Théorie des Jeux, dans lequel chaque joueur optimise sa propre fonction de coût qui dépend des actions des autres joueurs. Tout d’abord, nous étudions la capacité d’un encodeur et d’un décodeur à coordonner leurs actions avec les symboles générés par une source d’information. A cet effet, la suite d’actions de l’encodeur encapsule une version dégradée des symboles de source, qui sert à coordonner les futures actions du décodeur. Nous caractérisons les solutions de plusieurs instances du problème de coordination au Chap. IV, et au Chap. V, nous étendons ces résultats dans plusieurs directions, pour des problèmes de fuite d’état de canal, pour des problèmes de contrôle décentralisé et pour des problèmes de coordination forte. Le caractère stratégique de la transmission de l’information est étudié au Chap. VI lorsque les joueurs communiquent à travers un canal bruité. Nous considérons un encodeur s’engage à mettre en œuvre une stratégie, avant que les symboles de sources soient tirés, comme dans le jeu de persuasion Bayésienne. En guise de perspectives, nous étudierons l’impact des contraintes de communication sur la transmission d’informations stratégiques dans les problèmes de “mechanism design” de Jackson and Sonnenschein (2007), et dans les jeux de “cheap talk” de Crawford and Sobel (1982). Une autre direction de recherche consiste à approfondir les problèmes d’optimisation qui apparaissent pour le codage stratégique, en utilisant des outils issus de la Théorie des Graphes et de l’Optimisation Convexe. Nous pensons que ces résultats apporteront un point de vue nouveau sur les problèmes ouverts en jeux répétés avec observation imparfaite et information incomplète. L’objectif est de construire une théorie qui englobe les résultats de codage standard en théorie de l’information et les résultats pour les jeux “sender-receiver”.

International audience; Literature shows that trust typically relies on knowledge about the communication partner. Federated learning is an approach for collaboratively improving machine learning models. It allows collaborators to share Machine Learning models without revealing secrets, as only the abstract models and not the data used for their creation is shared. Federated learning thereby provides a mechanism to create trust without revealing secrets, such as specificities of local industrial systems. A fundamental challenge, however, is determining how much trust is justified for each contributor to collaboratively optimize the joint models. By assigning equal trust to each contribution, divergence of a model from its optimum can easily happen-caused by errors, bad observations, or cyberattacks. Trust also depends on how much an aggregated model contributes to the objectives of a party. For example, a model trained for an OT system is typically useless for monitoring IT systems. This paper shows first directions how heterogeneous distributed data sources could be integrated using federated learning methods. With an extended abstract, it shows current research directions and open issues from a cyber-analyst's perspective.

This paper provides a complete characterization of the information-energy region of simultaneous information and energy transmission over an additive white Gaussian noise channel in the finite block-length regime with finite sets of channel input symbols. Given a set of channel input symbols, the converse characterizes the tuples of information rate, energy rate, decoding error probability (DEP) and energy outage probability (EOP) that cannot be achieved by any code built using the given set of channel inputs. A novel method for constructing a family of codes that respects the given information rate, energy rate, DEP and EOP requirements is proposed. The achievable region identifies the set of tuples of information rate, energy rate, DEP and EOP that can be achieved by the constructed family of codes. The proposed construction proves to be information rate, energy rate, and EOP optimal. The achieved DEP is, however, sub-optimal, owing to the choice of the decoding regions made during the construction.

International audience; This paper characterizes the trade-offs between the information and energy transmission rates, the decoding error probability, and the energy outage probability in simultaneous information and energy transmission over an additive white Gaussian noise channel. The results in this paper take into account the impact of energy harvester (EH) non-linearities on the harvested energy. The analysis is carried out in the finite block-length regime with finite constellations. Improved converse and achievability bounds that account for the EH non-linearities are presented.

In this work, we investigate the problem of multiuser linearly separable function computation, where N servers help compute the desired functions (jobs) of K users. In this setting each desired function can be written as a linear combination of up to L (generally non-linear) sub-functions. Each server computes some of the sub-tasks, and communicates a linear combination of its computed outputs (files) in a singleshot to some of the users, then each user linearly combines its received data in order to recover its desired function. We explore the range of the optimal computation cost via establishing a novel relationship between our problem, syndrome decoding and covering codes. The work reveals that in the limit of large N , the optimal computation cost-in the form of the maximum fraction of all servers that must compute any subfunction-is lower bounded as γ ≥ H −1 q (log q (L) N), for any fixed log q (L)/N. The result reveals the role of the computational rate log q (L)/N , which cannot exceed what one might call the computational capacity Hq(γ) of the system.

Optimal rates for achieving an information processing task are often characterized in terms of regularized information measures. In many cases of quantum tasks, we do not know how to compute such quantities. Here, we exploit the symmetries in the recently introduced $D^{\#}$ in order to obtain a hierarchy of semidefinite programming bounds on various regularized quantities. As applications, we give a general procedure to give efficient bounds on the regularized Umegaki channel divergence as well as the classical capacity and two-way assisted quantum capacity of quantum channels. In particular, we obtain slight improvements for the capacity of the amplitude damping channel. We also prove that for fixed input and output dimensions, the regularized sandwiched R\'enyi divergence between any two quantum channels can be approximated up to an $\epsilon$ accuracy in time that is polynomial in $1/\epsilon$.

In this paper, we consider a perfect coordinated water-filling game, where each user transmits solely on a given carrier. The main goal of the proposed algorithm (which we call FEAT) is to get close to the optimal, while keeping a decent level of fairness. The key idea within FEAT is to minimize the ratio between the best and the worst utilities of the users. This is done by ensuring that, at each iteration (channel assignment), a user is satisfied with this assignment as long as he does not loose much more than other users in the system. It has been shown that FEAT outperforms most related algorithms in many aspects, especially in interference-limited systems. Indeed, with FEAT we can ensure a near-optimal, fair and energy efficient solution with low computational complexity. In terms of robustness, it turns out that the balance between being nearly globally optimal and good from individual point of view seems hard to sustain with a significant number of users. Also notice that, in this regard, global optimality gets less affected than the individual one, which offers hope that such an accurate water-filling algorithm can be designed around competition in interference-limited systems., 27 PAGES, 14 FIGURES

International audience; Coding algorithms usually compress independently the images of a collection, in particular when the correlation between them only resides at the semantic level, i.e., information related to the high-level image content. In this work, we propose a coding solution able to exploit this semantic redundancy to decrease the storage cost of data collections. First we introduce the multi-item compression framework. Then we derive a loss term to shape the latent space of a variational auto-encoder so that the latent vectors of semantically identical images can be aligned. Finally, we experimentally demonstrate that this alignment leads to a more compact representation of the data collection.

International audience; We study unsupervised Retinex decomposition for low light image enhancement. Being an underdetermined problem with infinite solutions, well-suited priors are required to reduce the solution space. In this paper, we analyze the characteristics of low-light images and their illumination component and identify a trivial solution not taken into consideration by the previous unsupervised state-of-the-art methods. The challenge comes from the fact that the trivial solution cannot be completely eliminated from the feasible set as it corresponds to the true solution when the low-light image contains a light source or an overexposed area. To address this issue, we propose a new regularization term which only remove absurd solutions and keep plausible ones in the set. To demonstrate the efficiency of the proposed prior, we conduct our experiments using deep image priors in a framework similar to the recent work RetinexDIP and an in-depth ablation study. Finally, we observe no more halo artefacts in the restored image. For all-but-one metrics, our unsupervised approach gives results as good as the supervised state-of-the-art indicating the potential of this framework for low-light image enhancement.

The automorphism group of the Zetterberg code Z of length 17 (also a quadratic residue code) is a rank three group whose orbits on the coordinate pairs determine two strongly regular graphs equivalent to the Paley graph attached to the prime 17. As a consequence, codewords of a given weight of Z are the characteristic vectors of the blocks of a PBIBD with two associate classes of cyclic type. More generally, this construction of PBIBDs is extended to quadratic residue codes of length $$\equiv 1 \pmod {8},$$ to the adjacency codes of triangular and lattice graphs, and to the adjacency codes of various rank three graphs. A remarkable fact is the existence of 2-designs held by the quadratic residue code of length 41 for code weights 9 and 10.

International audience; Access to high-quality data repositories and benchmarks have been instrumental in advancing the state of the art in many experimental research domains. While advanced analytics tasks over time series data have been gaining lots of attention, lack of such community resources severely limits scientific progress. In this paper, we present Exathlon, the first comprehensive public benchmark for explainable anomaly detection over high-dimensional time series data. Exathlon has been systematically constructed based on real data traces from repeated executions of large-scale stream processing jobs on an Apache Spark cluster. Some of these executions were intentionally disturbed by introducing instances of six different types of anomalous events (e.g., misbehaving inputs, resource contention, process failures). For each of the anomaly instances, ground truth labels for the root cause interval as well as those for the extended effect interval are provided, supporting the development and evaluation of a wide range of anomaly detection (AD) and explanation discovery (ED) tasks. We demonstrate the practical utility of Exathlon's dataset, evaluation methodology, and end-toend data science pipeline design through an experimental study with three state-of-the-art AD and ED techniques.

International audience; We lay the foundations of a non-parametric theory of best-arm identification in multi-armed bandits with a fixed budget T. We consider general, possibly non-parametric, models D for distributions over the arms; an overarching example is the model D = P(0,1) of all probability distributions over [0,1]. We propose upper bounds on the average log-probability of misidentifying the optimal arm based on information-theoretic quantities that correspond to infima over Kullback-Leibler divergences between some distributions in D and a given distribution. This is made possible by a refined analysis of the successive-rejects strategy of Audibert, Bubeck, and Munos (2010). We finally provide lower bounds on the same average log-probability, also in terms of the same new information-theoretic quantities; these lower bounds are larger when the (natural) assumptions on the considered strategies are stronger. All these new upper and lower bounds generalize existing bounds based, e.g., on gaps between distributions.

International audience; Claude Shannon, who laid the foundations of the celebrated information theory in 1948, preferred the term “communication theory”. In a 1953 paper, he proposed a new approach to information and its lattice structure. Surprisingly, this remained relatively unknown. We briefly recall the features of this theory and the characteristics that could explain its poor impact; finally we consider possible interesting developments.; Claude Shannon, qui a posé les bases de la célèbre théorie de l’information en 1948, préférait parler de théorie de la communication. Dans un article de 1953, il a proposé une nouvelle approche de l’information et de sa structure en treillis. Cela n’a étonnamment eu qu’un très faible écho. Nous rappelons brièvement les traits principaux de cette théorie et les caractéristiques qui pourraient en expliquer l’oubli, et nous envisageons enfin les développements intéressants qu’elle pourrait susciter.

We introduce a zero-error network source coding problem, in which an encoder transmits information to multiple decoders with different side-information (SI) and different desired source random variables. We give an inner and an outer bound for the achievable rate region. These bounds coincide in particular cases (e.g. constant SI). The inner bound relies on type classes, with covering and packing in type classes, and coset partitions; the zero-error property is ensured by a correcting argument., Nous présentons un problème de codage de source zéro-erreur, dans lequel un encodeur transmet de l'information à plusieurs décodeurs avec différentes informations adjacentes (abrégé en "SI" pour side-information) et différentes variables aléatoires demandées. Nous donnons une borne intérieure et extérieure pour la région des débits réalisables. De plus, nous explicitons des cas particuliers (par ex. SI constante), où ces bornes coïncident. La borne intérieure repose sur les classes de type, avec des lemmes de recouvrement et d'empilement dans ces classes ; la propriété zéro-erreur est garantie par un dispositif de correction.

International audience; Dans ce travail, nous considérons le problème de reconstruction de phase, qui consiste à recouvrer un signal de dimension n à partir des modules de ses m mesures linéaires. Nous présentons une nouvelle approche permettant de se passer de la Lipschitz continuité globale du gradient de l'objective non-convexe à minimiser. Pour ce faire, nous introduisons un algorithme de descente miroir non-euclidienne via la divergence de Bregman d'une entropie bien choisie. Nous montrons que lorsque le nombre de mesures m est suffisamment grand, alors avec grande probabilité, pour presque toute initialisation, l'algorithme de descente miroir, converge linéairement avec un taux indépendant de la dimension n, permettant ainsi de recouvrer le signal original à un changement de signe près. Nous énonçons nos résultats pour deux types de mesures: Gaussiennes iid et celles obtenues par des masques codés pour des transformées de Fourier aléatoires.