We study the problem of discrete distribution estimation under utility-optimized local differential privacy (ULDP), which enforces local differential privacy (LDP) on sensitive data while allowing more accurate inference on non-sensitive data. In this setting, we completely characterize the fundamental privacy–utility trade-off. The converse proof builds on several key ideas, including a generalized uniform asymptotic Cramér–Rao lower bound, a reduction showing that it suffices to consider a newly defined class of extremal ULDP mechanisms, and a novel distribution decomposition technique tailored to ULDP constraints. For the achievability, we propose a class of utility-optimized block design (uBD) schemes, obtained as nontrivial modifications of the block design mechanism known to be optimal under standard LDP constraints, while incorporating the distribution decomposition idea used in the converse proof and a score-based linear estimator. These results provide a tight characterization of the estimation accuracy achievable under ULDP and reveal new insights into the structure of optimal mechanisms for privacy-preserving statistical inference.

For multiple hypothesis testing based on classical data samples, we demonstrate a quantum advantage in the optimal privacy-utility trade-off (PUT), where the privacy and utility measures are set to (quantum) local differential privacy and the pairwise-minimum Chernoff information, respectively. To show the quantum advantage, we consider some class of hypotheses that we coin smoothed point masses. For such hypotheses, we derive an upper bound of the optimal PUT achieved by classical mechanisms, which is tight for some cases, and propose a certain quantum mechanism which achieves a better PUT than the upper bound. The proposed quantum mechanism consists of a classical-quantum channel whose outputs are pure states corresponding to a symmetric informationally complete positive operator-valued measure (SIC-POVM), and a depolarizing channel.

We consider a discrete distribution estimation problem under a local differential privacy (LDP) constraint in the presence of shared randomness. For this problem, we propose a new class of LDP schemes achieving the exactly optimal privacy-utility trade-off (PUT), with the communication cost less than or equal to the size of the input data. Moreover, it is shown as a simple corollary that one-bit communication is sufficient for achieving the exactly optimal PUT for a high privacy regime if the size of the input data is an even number. The main idea is to decompose a block design scheme proposed by Park et al. (2023), based on the combinatorial concept called resolution. We call the resultant decomposed LDP scheme with shared randomness as a resolution of the original block design scheme. A resolution of a block design scheme has a communication cost less than or equal to that of the original block design scheme. Also, the resolution of a block design scheme is exactly optimal whenever the original block design scheme is exactly optimal. Accordingly, we provide a resolution of the exactly optimal subset selection scheme proposed by Ye and Barg (2018), called the Baranyai's resolution. The Baranyai's resolution is not only exactly optimal, but also it achieves the minimum communication cost among all exactly optimal resolutions of block design schemes.

We consider a private discrete distribution estimation problem with one-bit communication constraint. The privacy constraints are imposed with respect to the local differential privacy. The estimation error is quantified by the worst-case mean squared error. We completely characterize the first-order asymptotics of this privacy-utility trade-off under the one-bit communication constraint by using ideas from local asymptotic normality and the resolution of a block design mechanism. This results demonstrate the optimal dependence of the privacy-utility trade-off under the one-bit communication constraint in terms of the privacy constraint and the size of the alphabet of the discrete distribution.

In this paper, we show that there is no advantage of using non-local cooperation between source encoders in improving the optimal compression rate (or rate region) for some canonical distributed compression tasks. The tasks are the lossless distributed compression, the lossless compression with a helper, and some special cases of the lossy distributed compression for 2-component discrete memoryless sources. These negative results for distributed source coding contrast with those for multi-user channel coding: quantum or general no-signaling cooperation between channel encoders improves the capacity region for some multiple access and interference channels.

We consider a private discrete distribution estimation problem with one-bit communication constraint. The privacy constraints are imposed with respect to the local differential privacy and the maximal leakage. The estimation error is quantified by the worst-case mean squared error. We completely characterize the first-order asymptotics of this privacy-utility trade-off under the one-bit communication constraint for both types of privacy constraints by using ideas from local asymptotic normality and the resolution of a block design mechanism. These results demonstrate the optimal dependence of the privacy-utility trade-off under the one-bit communication constraint in terms of the parameters of the privacy constraint and the size of the alphabet of the discrete distribution.

We consider a discrete distribution estimation problem under a local differential privacy (LDP) constraint in the presence of shared randomness. For this problem, we propose a new class of LDP schemes achieving the exactly optimal privacy-utility trade-off (PUT), with the communication cost less than or equal to the size of the input data. Moreover, it is shown as a simple corollary that one-bit communication is sufficient for achieving the exactly optimal PUT for a high privacy regime if the input data size is an even number. The main idea is to decompose a block design scheme proposed by Park et al. (2023), based on the combinatorial concept called resolution. We call the resultant decomposed LDP scheme with shared randomness as a resolution of the original block design scheme. A resolution of a block design scheme has a communication cost less than or equal to that of the original block design scheme. Also, the resolution of a block design scheme is exactly optimal whenever the original block design scheme is exactly optimal. Accordingly, we provide two resolutions of the exactly optimal subset selection scheme proposed by Ye and Barg (2018), called the Baranyai’s resolution and the cyclic shift resolution. We show that the Baranyai’s resolution achieves the minimum communication cost among all exactly optimal resolutions of block design schemes. One drawback of the Baranyai’s resolution is that its explicit structure is unknown in general. In contrast, the cyclic shift resolution has an explicit structure, but its communication cost can be larger than that of the Baranyai’s resolution. To complement this, we also suggest resolutions of other block design schemes achieving the exactly optimal PUT for some input data size and privacy budget. Those require the minimum communication cost as the Baranyai’s resolution and have explicit structures as the cyclic shift resolution.

In this paper, we propose a new class of local differential privacy (LDP) schemes based on combinatorial block designs for a discrete distribution estimation. This class not only recovers many known LDP schemes in a unified framework of combinatorial block design, but also suggests a novel way of finding new schemes achieving the optimal (or near-optimal) privacy-utility trade-off with lower communication costs. Indeed, we find many new LDP schemes that achieve both the optimal privacy-utility trade-off and the minimum communication cost among all the unbiased schemes for a certain set of input data size and LDP constraint. Furthermore, to partially solve the sparse existence issue of block design schemes, we consider a broader class of LDP schemes based on regular and pairwise-balanced designs, called RPBD schemes, which relax one of the symmetry requirements on block designs. By considering this broader class of RPBD schemes, we can find LDP schemes achieving near-optimal privacy-utility trade-off with reasonably low communication costs for a much larger set of input data size and LDP constraint.

We consider a discrete distribution estimation problem under the local differential privacy and the one-bit communication constraints. A fundamental privacy-utility tradeoff in this problem is formulated as the minimax squared loss. We show a tighter lower bound on the minimax squared loss, which has exactly the same form with the upper bound by the recursive Hadamard response by Chen et al. up to a constant factor of 4 for arbitrary LDP constraint and arbitrary finite data space. To derive the lower bound, we modify the van Trees inequality to involve a symmetrized Fisher information, which is invariant under the choice of the coordinate system on the probability simplex. We further characterize the maximum of the symmetrized Fisher information by considering the joint effect of the privacy and the communication constraints.

We consider a complex Gaussian wiretap channel with finite-resolution analog-to-digital converters (ADCs) at both the legitimate receiver and the eavesdropper. For this channel, we show that a positive secrecy rate is always achievable as long as the channel gains at the legitimate receiver and at the eavesdropper are different, regardless of the quantization levels of the ADCs. For the achievability, we first consider the case of the one-bit ADCs at the legitimate receiver and apply a binary input distribution where the two input points have the same phase when the channel gain at the legitimate receiver is less than that at the eavesdropper, and otherwise the opposite phase. Then the result is generalized for the case of arbitrary finite-resolution ADCs at the legitimate receiver by translating the input distribution appropriately. We also provide numerical lower bounds on the achievable secrecy rates, and analyze the tendency of the secrecy rates according to the channel difference, the power constraint, and the quantization levels for some cases. For the special case of the real Gaussian wiretap channel with one-bit ADCs at both the legitimate receiver and the eavesdropper, we show that our choice of phase does not lose any optimality for the Wyner code.

We consider the Gaussian wiretap channel with onebit analog-to-digital converters (ADCs) at both the legitimate receiver and the eavesdropper. In this channel, we show that a positive secrecy rate is always achievable whenever the noise power n12at the legitimate receiver is not the same as the noise power n22at the eavesdropper. A binary phase-shift keying (BPSK) and an asymmetric BPSK are shown to achieve a positive secrecy rate for the cases of n12and n1> n2, respectively. We partially justify the choice of these signalings by showing that the optimal input distribution that achieves Rs* := supPX:E[X2]≤PI(X; Y1) - I(X; Y2), where X is the channel input with power constraint of P, and Y1and Y2are the channel outputs at the legitimate receiver and the eavesdropper, respectively, should satisfy some symmetric and asymmetric properties for the cases of n12and n1> n2, respectively. Moreover, for n12and sufficiently large P, it is shown that a BPSK using power smaller than P achieves Rs*.