Symmetric multilevel diversity coding (SMDC) is a multi-source coding problem where the independent sources are ordered according to their importance. Prior work demonstrated thatsuperposition coding, where sources are encoded independently, is optimal. This paper investigates the(L,s)sliding secure SMDC problem, whereLrepresents the number of encoders andsis the security threshold. The security requirement dictates that each sourceXαmust be kept perfectly secure if no more than α –sencoders are accessible. The problem is specialized to the(L,s)multilevel secret sharingproblem when the firsts – 1sources are constants. Fors= 1, the two problems coincide, and we show that superposition coding is optimal. The rate regions for the(L,s)=(3,2)problems are characterized, which implies that superposition coding is suboptimal for the general case. The core insight for achieving lower rates through joint encoding is leveraging less important sources likeXα–1as secret keys for more important sources likeXα. Based on this idea, we propose a joint coding scheme that achieves the minimum sum rate of the general(L,s)multilevel secret sharing problem. Moreover, a pseudo-superposition coding scheme is proposed to achieve the minimum sum rate of the general sliding secure SMDC problem, which uses superposition coding for thessets of sourcesX1, X2,..., Xs–1, (Xs,Xs+1,XL)and joint coding amongXs,Xs+1,XL.

Consider a distributed coding for computing problem with constant decoding locality, i.e., with a vanishing error probability, any single sample of the function can be approximately recovered by probing only a constant number of compressed bits. We establish an achievable rate region by designing an efficient layered coding scheme, where the coding rate is reduced by introducing auxiliary random variables and local decoding is achieved by exploiting the expander graph code. Then we show the rate region is optimal under mild regularity conditions on source distributions. The proof relies on the reverse hypercontractivity and a rounding technique to construct auxiliary random variables. The rate region is strictly smaller than that for the classical problem without the constant locality constraint in most cases, which indicates that more rate is required in order to achieve lower coding complexity. Moreover, a coding for computing problem with side information is analogously studied. We also develop graph characterizations, which simplifies the computation of the achievable rate region.

This paper considers a real-time scheduling problem disseminating status update of sensors timely from a base station (BS) to users over wireless fading channels. The freshness of the updated status is quantified using the Age of Incorrect Information (AoII) metric. The objective is to minimize the long-term AoII under the constraint of limited transmission power, which necessitates that only a subset of users can successfully receive updates in each time slot. To find an optimal transmission policy, we first model the AoII minimization problem as a multi-action multi-armed bandit problem. After that, we decompose the derived MAB problem into multiple sub-problems. For each sub-problem, we obtain an optimal policy based on multiple threshold, thereby establishing the indexability of the optimal problem. Building upon this, a novel multi-action productivity index (MAPI) is introduced to get the optimal transmission policy. However, due to the computational complexity of the relative value iteration (RVI) algorithm, the exact value of the MAPI remains difficult to determine. To address this challenge, a computationally efficient algorithm is proposed to approximate the indices and derive the transmission policy for each user. Compared with Whittle’s Index and Max Weight policies, MAPI-based policy demonstrates significant performance improvement, particularly in large-scale networks and when the transmission power separation interval is small.

Consider the communication-constrained problem of nonparametric function estimation, in which each distributed terminal holds multiple i.i.d. samples. Under certain regularity assumptions, we characterize the minimax optimal rates for all regimes, and identify phase transitions of the optimal rates as the samples per terminal vary from sparse to dense. This fully solves the problem left open by previous works, whose scopes are limited to regimes with either dense samples or a single sample per terminal. To achieve the optimal rates, we design a layered estimation protocol by exploiting protocols for the parametric density estimation problem. We show the optimality of the protocol using information-theoretic methods and strong data processing inequalities, and incorporating the classic balls and bins model. The optimal rates are immediate for various special cases such as density estimation, Gaussian, binary, Poisson and heteroskedastic regression models.

For $\tilde f(t) = \exp \left( {\frac{{\alpha - 1}}{\alpha }t} \right)$, this paper shows that the Sibson mutual information is an α-leakage averaged over the adversary’s $\tilde f$ -mean relative information gain (on the secret) at elementary event of channel output Y as well as the joint occurrence of elementary channel input X and output Y . This interpretation is used to derive a sufficient condition that achieves a δ-approximation of ϵ-upper bounded α-leakage. A Y -elementary α-leakage is proposed, extending the existing pointwise maximal leakage to the overall Rényi order range α ∈ [0,∞). Maximizing this Y -elementary leakage over all attributes U of channel input X gives the Rényi divergence. Further, the Rényi capacity is interpreted as the maximal $\tilde f$-mean information leakage over both the adversary’s malicious inference decision and the channel input X (represents the adversary’s prior belief). This suggests an alternating max-max implementation of the existing generalized Blahut-Arimoto method.

This paper investigates the lazy secret sharing problem from an information-theoretic perspective. The participants are classified into two categories: Lazy-Participants and Share-Participants. The objective is to guarantee the perfect secret recovery from any t participants, while ensuring security exclusively for Share-Participants. The optimal coding rate region for lazy secret sharing is characterized. We further consider the imperfect security formulation, formulating security through information leakage constraints rather than strict security. The optimal rate region in the imperfect formulation is also established for a specific symmetric scenario.

A two-terminal lossy compression problem motivated by semantic communication is investigated, in which the semantic source is invisible at the encoders, two syntactic sources correlated with the semantic source are observed and compressed separately by two encoders, and a central decoder expects to reconstruct the semantic source and these two syntactic sources. The rate region of this semantic-aware quadratic Gaussian two-terminal source coding problem is characterized under the μ-sum assumption. This rate region is achieved by the Gaussian Berger-Tung coding scheme. The converse is proved by splitting the weighted-sum-rate optimization problem into sum-rate problem, CEO problem, and one-help-one problem to demonstrate the Gaussian optimality of weighted sum rate. This splitting method reveals the connection between the characterization of the whole rate region and the characterization of partial bounds, such as the sum-rate bound and the one-help-one bound.

The increasing demand for Extended Reality (XR) services in 6G networks calls for advanced wireless transmission systems capable of supporting immersive experience, sustainability, and stringent security and privacy guarantees. This paper investigates an energy-efficient XR transmission system that ensures high user-perceived quality under hard-latency constraints, while simultaneously meeting reliability and security requirements in the Finite Blocklength (FBL) regime. Specifically, the XR system is modeled as a finite-horizon Markov Decision Process (MDP), where a power allocation scheme is employed to satisfy FBL reliability and security requirements. Leveraging this MDP formulation, we construct a transmission power minimization problem subject to a user-perceived quality constraint that can maintain a stable playback rate at the receiver within a strict latency deadline. The minimum transmission power is then characterized through Bellman optimality equations of the value function, and the optimal XR transmission policy is derived using a Dynamic Programming (DP) approach. In addition, the proposed framework is extended to accommodate practical system non-idealities, including random XR traffic and context-aware reliability and security provisioning.

This paper investigates the challenge of acquiring channel state information at the transmitter (CSIT) in cell-free massive multiple-input multiple-output (MIMO) integrated sensing and communication (ISAC) systems operating in time-division duplex (TDD) mode. Although channel state information at the receiver (CSIR) is readily obtainable and CSIT is typically assumed to be its transpose, imperfections in the radio frequency (RF) chains disrupt this reciprocity. Focusing on this issue, we establish the necessary and sufficient conditions characterizing RF chain imperfections and their impact on system performance in a simplified scenario, underscoring the criticality of channel calibration. To address this challenge, a distributed source coding (DSC)-based calibration framework is proposed, leveraging the multiplexing of the sensing task to eliminate any additional communication overhead. This framework comprises a distributed compression scheme at each slave access point (AP) and a joint aggregation scheme at the central process unit (CPU). To validate the proposed DSC-based calibration framework, we analytically derive the performance gap relative to the fully collaborated approach. Building on this, a novel data-driven DSC-based deep learning method is proposed to address channel calibration without requiring clean labels. Numerical results demonstrate significant improvement in calibration performance achieved by our proposed method compared to existing calibration methods, approaching the performance of the fully collaborated method.

We define a graph-based rate optimization problem and consider its computation, which provides a unified approach to the computation of various theoretical limits, including the (conditional) graph entropy, rate-distortion functions and capacity-cost functions with side information. Compared with their classical counterparts, theoretical limits with side information are much more difficult to compute since their characterizations as optimization problems have larger and more complex feasible regions. Following the unified approach, we develop effective methods to resolve the difficulty. On the theoretical side, we derive graph characterizations for rate-distortion and capacity-cost functions with side information and simplify the characterizations in special cases by reducing the number of decision variables. On the computational side, we design an efficient alternating minimization algorithm for the graph-based problem, which deals with the inequality constraint by a flexible multiplier update strategy. Moreover, simplified graph characterizations are exploited and deflation techniques are introduced, so that the computing time is greatly reduced. Theoretical analysis shows that the algorithm converges to an optimal solution. By numerical experiments, the accuracy and efficiency of the algorithm are illustrated and its significant advantage over existing methods is demonstrated.

Symmetric multilevel diversity coding (SMDC) is a multi-source coding problem where the independent sources are ordered according to their importance. It was shown that sepa-rately encoding independent sources, referred to as superposition coding, is optimal. In this paper, an (L, s) sliding secure SMDC problem is considered, where$L$is the number of encoders and$s$is the security threshold, which means that each source$X$ais kept perfectly secure if no more than a -$s$encoders are accessible. It is shown that superposition coding is optimal for$s$= 1. The rate region for (L, s) = (3, 2) is characterized, which implies the suboptimality of superposition coding for the general problem. The main idea that joint coding can reduce rates is that we can use the previous source X a -1 as the secret key of X a. Based on this idea, a pseudo-superposition coding scheme is proposed to achieve the minimum sum rate, which uses superposition for the$s$sets of sources Xl, X2,‥ Xs-1, (Xs, Xs+1,”, XL). and joint encoding among Xs, Xs+1,”, XL.

Consider a distributed coding for computing problem with constant decoding locality, i.e., with a vanishing error probability, any single sample of the function can be approximately recovered by probing only constant number of compressed bits. We establish an achievable rate region by designing an efficient layered coding scheme, where the coding rate is reduced by introducing auxiliary random variables and local decoding is achieved by exploiting the expander graph code. Then we show the rate region is optimal under mild regularity conditions on source distributions. The proof relies on the reverse hypercontractivity and a rounding technique to construct auxiliary random variables. The rate region is strictly smaller than that for the classical problem without the constant locality constraint in most cases, which indicates that more rate is required in order to achieve lower coding complexity. Graph characterizations are also developed to simplify the computation of the achievable rate region.

The problem of joint information and noisy Gaussian state amplification is investigated in this paper. The optimal capacity-distortion tradeoff is characterized. For the achievability part, the Gelfand-Pinsker scheme is evaluated using minimum mean squared error of Gaussian random variables. For the converse part, Cauchy-Schwartz inequality is invoked to transform the optimal linear estimation into a canonical form.

Group testing is a technique that can reduce the number of tests needed to identify infected members in a population, by pooling together multiple diagnostic samples. Despite the variety and importance of prior results, traditional work on group testing has typically assumed independent infections. However, contagious diseases among humans, like SARS-CoV-2, have an important characteristic: infections are governed by community spread, and are therefore correlated. In this paper, we explore this observation and we argue that taking into account the community structure when testing can lead to significant savings in terms of the number of tests required to guarantee a given identification accuracy. To show that, we start with a simplistic (yet practical) infection model, where the entire population is organized in (possibly overlapping) communities and the infection probability of an individual depends on the communities (s)he participates in. Given this model, we compute new lower bounds on the number of tests for zero-error identification and design community-aware group testing algorithms that can be optimal under assumptions. Finally, we demonstrate significant benefits over traditional, community-agnostic group testing via simulations using both noiseless and noisy tests. Shorter versions of this article, which contained a subset of the material, were presented in the work by Nikolopoulos et al. (2021, 2021).

We consider a semantic cipher system, in which we protect only the semantic information of the source. The optimal tradeoff is characterized among the coding rate, the secret key rate, the semantic information leakage rate, the source reconstruction distortion, and the semantic distortion. It is shown that an efficient key with a small size suffices to protect the semantic information.

We study an estimation-compression (EC) separation scheme in a semantic communication system. Therein, the semantic information is intrinsic and not observable. The EC scheme first estimates the semantic information from the observed message and then compresses the estimation subject to a rate-distortion regime. The corresponding EC rate-distortion tradeoff is obtained. In particular, the EC separation scheme achieves the semantic rate-distortion function if the estimation is a sufficient statistic of the semantic information based on the observed message. Moreover, the extra distortion incurred by the compression in addition to the irreducible error in semantic estimation problems is also analyzed. A binary classification of vector Gaussian observations is investigated. We design an optimal soft decision estimator which is a sufficient statistic and show that it strictly outperforms the Bayesian decision estimator in terms of rate-distortion tradeoff. As the dimension of the observed Gaussian vector increases, the performance gap between the Bayesian decision estimator and the soft decision estimator becomes smaller and smaller until it is negligible.

We consider a problem of coding for computing, where the decoder wishes to estimate a function of its local message and the source message at the encoder within a given distortion. We show that the rate-distortion function can be characterized through a characteristic multi-hypergraph, which simplifies the evaluation of the rate-distortion function.

In this paper, we propose algorithms that leverage a known community structure to make group testing more efficient. We consider a population organized in disjoint communities: each individual participates in a community, and its infection probability depends on the community (s)he participates in. Use cases include families, students who participate in several classes, and workers who share common spaces. Group testing reduces the number of tests needed to identify the infected individuals by pooling diagnostic samples and testing them together. We show that if we design the testing strategy taking into account the community structure, we can significantly reduce the number of tests needed for adaptive and non-adaptive group testing, and can improve the reliability in cases where tests are noisy.

In this paper, we propose algorithms that leverage a known community structure to make group testing more efficient. We consider a population organized in connected communities: each individual participates in one or more communities, and the infection probability of each individual depends on the communities (s)he participates in. Use cases include students who participate in several classes, and workers who share common spaces. Group testing reduces the number of tests needed to identify the infected individuals by pooling diagnostic samples and testing them together. We show that making testing algorithms aware of the community structure, can significantly reduce the number of tests needed both for adaptive and non-adaptive group testing.

In this paper, we introduce an n-channel multilevel imperfect secret sharing problem, which can be regarded as a generalization of secret sharing and a variation of multilevel diversity coding. In this model, a discrete memoryless source (DMS) is encoded into n encoded messages. To measure the secrecy of the system, we introduce a security level for each subset of encoded messages. In the paper, we focus on the n-channel symmetric multilevel imperfect secret sharing (SMISS) problem, i.e., the security levels of all the subsets with the same cardinality are identical. First, we explicitly characterize the coding rate regions for 2-channel and 3-channel SMISS problems. However, it is difficult to characterize the explicit rate region for a general n, since the complexity of designing optimal coding schemes can grow with n exponentially. Nevertheless, we put forward an inner bound and an outer bound on the rate region of the general n-channel SMISS problem. Moreover, we consider two special cases, i.e., the Two-SMISS problem and the linear SMISS problem, and prove that the inner and outer bounds are tight for these two problems, respectively.

We consider information leakage to the user in private information retrieval (PIR) systems. Information leakage can be measured in terms of individual message leakage or total leakage. Individual message leakage, or simply individual leakage, is defined as the amount of information that the user can obtain on any individual message that is not being requested, and the total leakage is defined as the amount of information that the user can obtain about all the other messages except the one being requested. In this work, we characterize the tradeoff between the minimum download cost and the individual leakage, and that for the total leakage, respectively. Coding schemes are proposed to achieve these optimal tradeoffs, which are also shown to be optimal in terms of the message size. We further characterize the optimal tradeoff between the minimum amount of common randomness and the total leakage. Moreover, we show that under individual leakage, common randomness is in fact unnecessary when there are more than two messages.

In the canonical private information retrieval (PIR) problem, a user retrieves a message from a set of databases without allowing any individual database to obtain any knowledge regarding the identity of the requested message. This perfect privacy requirement may be too stringent in many cases, and the user may only wish to control the amount of the privacy leakage to below a given level, and in return, can retrieve the message at a lower communication cost. In this work, we study the tradeoff between the download cost and the amount of privacy leakage under the maximal leakage metric. A new scheme is proposed by allowing a more flexible query structure and probability distributions in a code previously proposed by Tian et al., which utilized a fixed query set and a uniform distribution. It is shown that the optimal probability distribution in the proposed scheme has a particularly simple structure, which leads to a closed form achievability bound for the optimal tradeoff between the download cost and the privacy leakage. The proposed scheme includes several known schemes, such as those proposed by Lin et al., by Samy et al., and by Jia, as special cases.

We consider information leakage to the user in private information retrieval (PIR) systems. Information leakage can be measured in terms of individual message leakage or total leakage. Individual message leakage, or simply individual leakage, is defined as the amount of information that the user can obtain on any individual message that is not being requested, and the total leakage is defined as the amount of information that the user can obtain about all the other messages except the one being requested. In this work, we characterize the tradeoff between the minimum download cost and the individual leakage, and that for the total leakage, respectively. Coding schemes are proposed to achieve these optimal tradeoffs, which are also shown to be optimal in terms of the message size. We further characterize the optimal tradeoff between the minimum amount of common randomness and the total leakage. Moreover, we show that under individual leakage, common randomness is in fact unnecessary when there are more than two messages.

Multilevel diversity coding is a classical coding model where multiple mutually independent information messages are encoded, such that different reliability requirements can be afforded to different messages. It is well known that superposition coding, namely separately encoding the independent messages, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999). In the current paper, we consider weakly secure SMDC where security constraints are injected on each individual message, and provide a complete characterization of the conditions under which superposition coding is sum-rate optimal. Two joint coding strategies, which lead to rate savings compared to superposition coding, are proposed, where some coding components for one message can be used as the encryption key for another. By applying different variants of Han's inequality, we show that the lack of opportunity to apply these two coding strategies directly implies the optimality of superposition coding. It is further shown that under a set of particular security constraints, one of the proposed joint coding strategies can be used to construct a code that achieves the optimal rate region.

Multilevel diversity coding is a classical coding model where multiple mutually independent information messages are encoded, such that different reliability requirements can be afforded to different messages. It is well known that superposition coding, namely separately encoding the independent messages, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999). In the current paper, we consider weakly secure SMDC where secrecy constraints are injected on each individual message, and provide a complete characterization of the conditions under which superposition coding is sum-rate optimal. Two joint coding strategies, which lead to rate savings compared to superposition coding, are proposed, where some coding components for one message can be used as the encryption key for another. By applying different variants of Han's inequality, we show that the lack of opportunities to apply these two coding strategies directly implies the optimality of superposition coding. It is further shown that under a particular security configuration, one of the proposed joint coding strategies can be used to achieve the optimal sum rate.

It is well known thatsuperposition coding, namely separately encoding the independent sources, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999). However, the characterization of the coding rate region therein involves uncountably many linear inequalities and the constant term (i.e., the lower bound) in each inequality is given in terms of the solution of a linear optimization problem. Thus this implicit characterization of the coding rate region does not enable the determination of the achievability of a given rate tuple. In this paper, we first obtain closed-form expressions of these uncountably many inequalities. Then we identify a finite subset of inequalities that is sufficient for characterizing the coding rate region. This gives an explicit characterization of the coding rate region. We further show by the symmetry of the problem that only a much smaller subset of this finite set of inequalities needs to be verified in determining the achievability of a given rate tuple. Yet, the cardinality of this smaller set grows at least exponentially fast withL.

We generalize secret sharing to a symmetric multilevel imperfect secret sharing (SMISS) problem. To measure the secrecy of the system, we introduce a security level for each set of encoded messages, which is measured by the equivocation of the source message given the encoded messages in this set. The security levels of all the subsets with the same cardinality are assumed to be identical. This problem in its general case is complicated. In this paper, we explicitly characterize the rate regions of the general two-level and three-level SMISS problems.