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.

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.

We consider the computation of the entanglement-assisted quantum rate-distortion function, which plays a central role in quantum information theory. We propose an efficient alternating minimization algorithm based on the Lagrangian analysis. Instead of fixing the multiplier corresponding to the distortion constraint, we update the multiplier in each iteration. Hence the algorithm solves the original problem itself, rather than the Lagrangian relaxation of it. Moreover, all the other variables are iterated in closed form without solving multidimensional nonlinear equations or multivariate optimization problems. Numerical experiments show the accuracy of our proposed algorithm and its improved efficiency over existing methods.

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.

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.

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.

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.