We study the problem of unbiased minimum mean squared error quantization of the $L_1$ ball, with applications to distributed mean estimation and federated learning. Inspired by quantization of probability distributions using types, we design a novel computationally efficient unbiased quantization scheme for vectors that lie within the $L_1$ ball. We also derive upper bounds on the worst-case mean squared error achieved by our scheme and show that this is order optimal. We then use this to design polynomial (in the dimension of the input vectors)-time schemes for communication-efficient distributed mean estimation and distributed/federated learning, and demonstrate its effectiveness using simulations.

It is shown that a memoryless source can be compressed arbitrarily close to its entropy rate while guaranteeing the private local decoding of any source symbol. This is achieved through a remarkably simple compression scheme that effectively separates compression and privacy.

A fixed-length compression scheme is said to be locally decodable if any bit of the source sequence can be recovered by probing only a small subset of the compressed bits. A recent work addressed the problem of private locally decodable compression: Is it possible to compress a source$X^{n}$such that the compressed bits probed by the local decoder to recover any$X_{i}$reveal no information about the remainder of the source sequence$\{X_{j}:j\neq i\}$? A compression scheme was proposed that achieved a non-trivial rate and private local decoding, but it remained unclear whether the gap to entropy was inherent to the privacy property or not. We show that private local decodability is not a fundamental impediment to compression, and prove the existence of an entropy-achieving compression scheme for i.i.d. bit strings that guarantees the private local decodability of any individual source symbol.

We derive lower bounds on the maximal rates for multiple packings in high-dimensional Euclidean spaces. For any$ N > 0 $and$ L\in \mathbb {Z}_{\ge 2} $, a multiple packing is a set$\mathcal {C}$of points in$ \mathbb {R}^{n} $such that any point in$ \mathbb {R}^{n} $lies in the intersection of at most$ L-1 $balls of radius$ \sqrt {nN} $around points in$ \mathcal {C} $. This is a natural generalization of the sphere packing problem. We study the multiple packing problem for both bounded point sets whose points have norm at most$\sqrt {nP}$for some constant$P > 0$, and unbounded point sets whose points are allowed to be anywhere in$ \mathbb {R}^{n} $. Given a well-known connection with coding theory, multiple packings can be viewed as the Euclidean analog of list-decodable codes, which are well-studied over finite fields. We derive the best known lower bounds on the optimal multiple packing density. This is accomplished by establishing an inequality which relates the list-decoding error exponent for additive white Gaussian noise channels, a quantity of average-case nature, to the list-decoding radius, a quantity of worst-case nature. We also derive novel bounds on the list-decoding error exponent for infinite constellations and closed-form expressions for the list-decoding error exponents for the power-constrained AWGN channel, which may be of independent interest beyond multiple packing.

Classical compression schemes suggest that message symbols cannot be privately decoded; if a string Xnis encoded into a codeword CnRat a non-trivial rate R, then the decoding of an individual symbol Xireveals information about the rest of the symbols Xn\Xi.While this holds for virtually all lossless compression schemes, it is shown that this need not be the case. This paper proposes a lossless compression scheme for bit strings with the following properties. For any sufficiently small p > 0, it encodes each length-n bit string of Hamming weight at most np into a binary codeword of length $O\left( {np{{\log }^2}\frac{1}{p}} \right)$ such that the subset of compressed bits that need to be probed in order to decode a particular message bit reveals no additional information about the other message bits.

We study the problem of high-dimensional multiple packing in Euclidean space. Multiple packing is a natural generalization of sphere packing and is defined as follows. Let$N>0 $and$L\in \mathbb {Z}_{\ge 2} $. A multiple packing is a set$\mathcal {C}$of points in$\mathbb {R}^{n} $such that any point in$\mathbb {R}^{n} $lies in the intersection of at most$L-1 $balls of radius$\sqrt {nN} $around points in$\mathcal {C} $. Given a well-known connection with coding theory, multiple packings can be viewed as the Euclidean analog of list-decodable codes, which are well-studied for finite fields. In this paper, we derive the best known lower bounds on the optimal density of list-decodable infinite constellations for constant$L$under a stronger notion called average-radius multiple packing. To this end, we apply tools from high-dimensional geometry and large deviation theory.

This paper investigates the Slepian-Wolf distributed compression of two sources Xnand Ynwith the additional property that any pair (Xi, Yi) should reliably be decoded by probing a small number d of compressed bits. We show that for certain source distributions, the error probability of any such local decoder is lower bounded by 2–O(d), in the worst case over index i, whenever one of the sources is compressed below its entropy. Unlike the single-source setup, it is thus impossible to simultaneously achieve constant local decodability d and vanishing local decoding error probability as n increases. We also provide a compression scheme with a local decoder that almost achieves the above lower bound.

We study the problem of characterizing the maximal rates of list decoding in Euclidean spaces for finite list sizes. For any positive integer L ≥ 2 and real N > 0, we say that a subset $\mathcal{C} \subset {\mathbb{R}^n}$ is an (N,L – 1)-multiple packing or an (N,L– 1)-list decodable code if every Euclidean ball of radius $\sqrt {nN} $ in ℝncontains no more than L − 1 points of C. We study this problem with and without ℓ2norm constraints on $\mathcal{C}$, and derive the best-known lower bounds on the maximal rate for (N,L−1) multiple packing. Our bounds are obtained via error exponents for list decoding over Additive White Gaussian Noise (AWGN) channels. We establish a curious inequality which relates the error exponent, a quantity of average-case nature, to the list-decoding radius, a quantity of worst-case nature. We derive various bounds on the error exponent for list decoding in both bounded and unbounded settings which could be of independent interest beyond multiple packing.

We study the problem of high-dimensional multiple packing in Euclidean space. Multiple packing is a natural generalization of sphere packing and is defined as follows. Let N > 0 and $L \in {\mathbb{Z}} \geq 2$. A multiple packing is a set ${\mathcal{C}}$ of points in ${{\mathbb{R}}^n}$ such that any point in ${{\mathbb{R}}^n}$ lies in the intersection of at most L – 1 balls of radius $\sqrt {nN} $ around points in ${\mathcal{C}}$. Given a well-known connection with coding theory, multiple packings can be viewed as the Euclidean analog of list-decodable codes, which are well-studied for finite fields. In this paper, we exactly pin down the asymptotic density of (expurgated) Poisson Point Processes under a stronger notion called average-radius multiple packing. To this end, we apply tools from high-dimensional geometry and large deviation theory. This gives rise to the best known lower bound on the largest multiple packing density. Our result corrects a mistake in a previous paper by Blinovsky [Bli05].

We study the problem of high-dimensional multiple packing in Euclidean space. Multiple packing is a natural generalization of sphere packing and is defined as follows. Let P, N > 0 and $L \in {{\mathbb{Z}}_{ \geq 2}}$. A multiple packing is a set ${\mathcal{C}}$ of points in ${{\mathcal{B}}^n}(\underline{0} ,\sqrt {nP} )$ such that any point in ℝnlies in the intersection of at most L – 1 balls of radius $\sqrt {nN} $ around points in ${\mathcal{C}}$.1In this paper, we derive two lower bounds on the largest possible density of a multiple packing. These bounds are obtained through a stronger notion called average-radius multiple packing. Specifically, we exactly pin down the asymptotics of (expurgated) Gaussian codes and (expurgated) spherical codes under average-radius multiple packing. To this end, we apply tools from high-dimensional geometry and large deviation theory. The bound for spherical codes matches the previous best known bound which was obtained for the standard (weaker) notion of multiple packing through a curious connection with error exponents [Bli99], [ZV21]. The bound for Gaussian codes suggests that they are strictly inferior to spherical codes.

We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints$P $and$N $respectively, the list decoding capacity is equal to$\frac {1}{2}\log \frac {P}{N}$. Random spherical codes achieve constant list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain conjecture that originates in analytic number theory is true, then the list size grows as a polynomial function of the gap-to-capacity.

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most$2\log (n)$bits in one sub-regime, and at most$\Omega ({n})$bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability, and a Plotkin-type push attack for the converse in a subregion of the NSRs, both of which may be of independent interest. We also give bounds on the strong secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping.

In this article, we revisit the classical problem of channel coding and obtain novel results on properties of capacity- achieving codes. Specifically, we give a linear algebraic characterization of the set of capacity-achieving input distributions for discrete memoryless channels. This allows us to characterize the dimension of the manifold on which the capacity-achieving distributions lie. We then proceed by examining empirical properties of capacity-achieving codebooks by showing that the joint-type of k-tuples of codewords in a good code must be close to the k- fold product of the capacity-achieving input distribution. While this conforms with the intuition that all capacity-achieving codes must behave like random capacity-achieving codes, we also show that some properties of random coding ensembles do not hold for all codes. We prove this by showing that there exist pairs of communication problems such that random code ensembles simultaneously attain capacities of both problems, but certain (superposition ensembles) do not.Due to lack of space, several proofs have been omitted but can be found at https://sites.google.com/view/yihan/ [1]

This paper addresses the problem of data compression with local decoding and local update. A compression scheme has worst-case local decoding dwcif any bit of the raw file can be recovered by probing at most dwcbits of the compressed sequence, and has update efficiency of uwcif a single bit of the raw file can be updated by modifying at most uwcbits of the compressed sequence. This article provides an entropy-achieving compression scheme for memoryless sources that simultaneously achieves O (log log n) local decoding and update efficiency. Key to this achievability result is a novel succinct data structure for sparse sequences which allows efficient local decoding and local update. Under general assumptions on the local decoder and update algorithms, a converse result shows that the maximum of dwcand uwcmust grow as Ω(log log n).

We study achievable rates of reliable communication in a power-constrained two-way additive interference channel over the real alphabet where communication is disrupted by a power-constrained jammer. This models the wireless communication scenario where two users Alice and Bob, operating in the full duplex mode, wish to exchange messages with each other in the presence of a jammer, James. Alice and Bob simultaneously transmit their encodings xAand xBover n channel uses. It is assumed that James can choose his jamming signal s as a noncausal randomized function of xA+ xB, and the codebooks used by Alice and Bob. Alice and Bob observe xA+ xB+ s, and must recover each others' messages reliably. In this article, we provide upper and lower bounds on the capacity of this channel which match each other and equal 1/2 log (1/2 + SNR) in the high-SNR regime (where SNR, signal to noise ratios, is defined as the ratio of the power constraints of the users to the power constraint of the jammer). We give a code construction based on lattice codes, and derive achievable rates for large SNR. We also present upper bounds based on two specific attack strategies for James. Along the way, sumset property of lattices for the achievability and general properties of capacity-achieving codes for memoryless channels for the converse are proved, which might be of independent interest. The full version of this paper is [1].

This paper investigates data compression that simultaneously allows local decoding and local update. The main result is a universal compression scheme for memoryless sources with the following features. The rate can be made arbitrarily close to the entropy of the underlying source, contiguous fragments of the source can be recovered or updated by probing or modifying a number of codeword bits that is on average linear in the size of the fragment, and the overall encoding and decoding complexity is quasilinear in the blocklength of the source. In particular, the local decoding or update of a single message symbol can be performed by probing or modifying on average a constant number of codeword bits. This latter part improves over previous best known results for which local decodability or update efficiency grows logarithmically with blocklength.

In compressing large datasets it is often desirable to guarantee locality properties that allow the efficient decoding and efficient update of short fragments of data. This paper proposes a universal compression scheme for memoryless sources with the following features: 1. the rate can be made arbitrarily close to the entropy of the underlying source, 2. constant-sized (as a function of the blocklength) fragments of the source can be recovered by probing a constant number of codeword bits on average, 3. the update of constant-sized fragments of the source can be achieved by reading and modifying a constant number of codeword symbols on average, and 4. the overall encoding and decoding complexity is quasilinear in the blocklength of the source.

We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints P and N respectively, the list decoding capacity is equal to z log Ñ. Random spherical codes achieve capacity with constant (as a function of the blocklength) list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain number-theoretic conjecture is true, then the list size grows as a polynomial function of the gap-to-capacity.

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is assumed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most O(log(n)) bits in one sub-regime, and at most O(n) bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques include a novel myopic list-decoding result for achievability and a Plotkin-type push attack for the converse in a subregion of the NSRs, which may be of independent interest.

In this article, we study the problem of secret key generation in the multiterminal source model, where the terminals have access to correlated Gaussian sources. We assume that the sources form a Markov chain on a tree. We give a nested lattice-based key generation scheme whose computational complexity is polynomial in the number, N, of independent and identically distributed samples observed by each source. We also compute the achievable secret key rate and give a class of examples where our scheme is optimal in the fine quantization limit. However, we also give examples that show that our scheme is not always optimal in the limit of fine quantization.

We study the problem of estimating the pattern maximum likelihood (PML) distribution for time-homogeneous discrete-time Markov chains (DTMCs). The PML problem for memoryless sources has been well studied in the literature and we propose an extension of the same for DTMCs. For memoryless sources, Acharya et al. have shown that plug-in estimators obtained from the PML estimate yield good estimates for symmetric functionals of the distribution. We show that this holds for the PML estimate of DTMCs as well. Finally, we express the PML estimate for DTMCs as the double minimization of a certain free energy function and discuss some mean-field approximations to approximate the PML estimate efficiently.

We study some structural properties of Construction-A lattices obtained from low-density parity-check (LDPC) codes over prime fields. Such lattices are called low-density Construction-A (LDA) lattices, and have been shown to achieve the capacity of the AWGN channel under closest lattice-point decoding. Also, simulations suggest that they perform well under belief propagation decoding. In this work, we prove that LDA lattices are good for packing and mean squared error (MSE) quantization, and that their duals are good for packing. With this, we can conclude that codes constructed using nested LDA lattices can achieve the capacities of the AWGN channel and the dirty paper channel, the rates guaranteed by the compute-and-forward protocol, and the best known rates for bidirectional relaying with perfect secrecy.

The basic problem of secure bidirectional relaying involves two users who want to exchange messages via an intermediate “honest-but-curious” relay node. There is no direct link between the users; all communication must take place via the relay node. The links between the user nodes and the relay are wireless links with Gaussian noise. It is required that the users' messages be kept secure from the relay. In prior work, we proposed coding schemes based on nested lattices for this problem, assuming that the channel gains from the two user nodes to the relay are identical. We also analyzed the power-rate tradeoff for secure and reliable message exchange using our coding schemes. In this paper, we extend our prior work to the case when the channel gains are not necessarily identical, and are known to the relay node but perhaps not to the users. We show that using our scheme, perfect secrecy can be obtained only for certain values of the channel gains, and analyze the power-rate tradeoff in these cases. We also make similar observations for our strongly-secure scheme.

We consider the basic bidirectional relaying problem, in which two users in a wireless network wish to exchange messages through an intermediate relay node. In the compute-and-forward strategy, the relay computes a function of the two messages using the naturally occurring sum of symbols simultaneously transmitted by user nodes in a Gaussian multiple-access channel (MAC), and the computed function value is forwarded to the user nodes in an ensuing broadcast phase. In this paper, we study the problem under an additional security constraint, which requires that each user's message be kept secure from the relay. We consider two types of security constraints: 1) perfect secrecy, in which the MAC channel output seen by the relay is independent of each user's message and 2) strong secrecy, which is a form of asymptotic independence. We propose a coding scheme based on nested lattices, the main feature of which is that given a pair of nested lattices that satisfy certain goodness properties, we can explicitly specify probability distributions for randomization at the encoders to achieve the desired security criteria. In particular, our coding scheme guarantees perfect or strong secrecy even in the absence of channel noise. The noise in the channel only affects reliability of computation at the relay, and for Gaussian noise, we derive achievable rates for reliable and secure computation. We also present an application of our methods to the multihop line network in which a source needs to transmit messages to a destination through a series of intermediate relays.