Search

To reduce the communication cost of differential privacy mechanisms, we introduce a novel construction, called Poisson private representation (PPR), designed to compress and simulate any local randomizer while ensuring local differential privacy. Unlike previous simulation-based local differential privacy mechanisms, PPR exactly preserves the joint distribution of the data and the output of the original local randomizer. Hence, the PPR-compressed privacy mechanism retains all desirable statistical properties of the original privacy mechanism such as unbiasedness and Gaussianity. Moreover, PPR achieves a compression size within a logarithmic gap from the theoretical lower bound. Using the PPR, we give a new order-wise trade-off between communication, accuracy, central and local differential privacy for distributed mean estimation. Experiment results on distributed mean estimation show that PPR consistently gives a better trade-off between communication, accuracy and central differential privacy compared to the coordinate subsampled Gaussian mechanism, while also providing local differential privacy., Comment: 30 pages, 3 figures

We present a unified one-shot coding framework designed for communication and compression of messages among multiple nodes across a general acyclic noisy network. Our setting can be seen as a one-shot version of the acyclic discrete memoryless network studied by Lee and Chung, and noisy network coding studied by Lim, Kim, El Gamal and Chung. We design a proof technique, called the exponential process refinement lemma, that is rooted in the Poisson matching lemma by Li and Anantharam, and can significantly simplify the analyses of one-shot coding over multi-hop networks. Our one-shot coding theorem not only recovers a wide range of existing asymptotic results, but also yields novel one-shot achievability results in different multi-hop network information theory problems. In a broader context, our framework provides a unified one-shot bound applicable to any combination of source coding, channel coding and coding for computing problems.

We consider a generalized collision channel model for general multi-user communication systems, an extension of Massey and Mathys' collision channel without feedback for multiple access communications. In our model, there are multiple transmitters and receivers sharing the same communication channel. The transmitters are not synchronized and arbitrary time offsets between transmitters and receivers are assumed. A ``collision" occurs if two or more packets from different transmitters partially or completely overlap at a receiver. Our model includes the original collision channel as a special case. This paper focuses on reliable throughputs that are approachable for arbitrary time offsets. We consider both slot-synchronized and non-synchronized cases and characterize their reliable throughput regions for the generalized collision channel model. These two regions are proven to coincide. Moreover, it is shown that the protocol sequences constructed for multiple access communication remain ``throughput optimal" in the generalized collision channel model. We also identify the protocol sequences that can approach the outer boundary of the reliable throughput region.

In this paper, we introduce a new class of codes, called weighted parity-check codes, where each parity-check bit has a weight that indicates its likelihood to be one (instead of fixing each parity-check bit to be zero). It is applicable to a wide range of settings, e.g. asymmetric channels, channels with state and/or cost constraints, and the Wyner-Ziv problem, and can provably achieve the capacity. For the channels with state (Gelfand-Pinsker) setting, the proposed coding scheme has two advantages compared to the nested linear code. First, it achieves the capacity of any channel with state (e.g. asymmetric channels). Second, simulation results show that the proposed code achieves a smaller error rate compared to the nested linear code. We also discuss a sparse construction where the belief propagation algorithm can be applied to improve the coding efficiency., Comment: 17 pages, 4 figure. This is the full version of a paper presented at 2022 IEEE International Symposium on Information Theory (ISIT)

This paper focuses on the link scheduling problem in networks where signal delays between nodes are multiples of a time interval. To model such networks, a directed hypergraph is employed, along with an integer matrix that specifies the delays. The link scheduling problem is closely connected to the independent sets of the periodic hypergraph induced by the network model. However, due to the infinite number of vertices, it is impractical to enumerate the independent sets of the periodic hypergraph using generic graph algorithms. To tackle this challenge, a graphical approach is proposed in this paper. The link scheduling rate region is characterized using a finite directed graph called a scheduling graph, which is derived from the network model. A collision-free schedule of the network corresponds to a path in the scheduling graph, and the rate region is determined by the convex hull of the rate vectors associated with the cycles in the scheduling graph. Although existing cycle enumeration algorithms can be employed to calculate the rate region, their computational complexity becomes prohibitively high as the size of the scheduling graph grows exponentially with the number of network links. To address this issue, the dominance property of a special scheduling graph called the step-T scheduling graph is investigated. This property allows the utilization of specific subgraphs of the step-T scheduling graph to characterize the scheduling rate region, achieving a reduction in both the number of cycles and their lengths. For common problems such as calculating the rate region and maximizing a weighted sum of the scheduling rates, algorithms leveraging the dominance property are developed. These algorithms can be more efficient than using generic graph algorithms directly on the scheduling graphs., Comment: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Using the 135-second cadence of the photospheric vector data provided by the Helioseismic and Magnetic Imager telescope on board the Solar Dynamic Observatory, we examined the time-evolution of magnetic helicity fluxes across the photosphere during 16 flares with the energy class lower than M5.0. During the flare in 4 out of 16 events, we found impulsive changes in the helicity fluxes. This indicates that even the flare with less energy could be associated with anomalistic transportation of the magnetic helicity across the photosphere. Accompanying the impulsive helicity fluxes, the poynting fluxes across the photosphere evolved from positive to negative. As such, the transportations of magnetic energy across the photosphere were toward solar interior during these flares. In each of the 4 events, the impulsive change in the helicity flux was always mainly contributed by abrupt change in horizontal velocity field on a sunspot located near the flaring polarity inversion line. The velocity field on each sunspot shows either an obvious vortex patten or an shearing patten relative to the another magnetic polarity, which tended to relax the magnetic twist or shear in the corona. During these flares, abrupt change in the Lorentz force acting on these sunspots were found. The rotational motions and shearing motions of these sunspots always had the same directions with the resultant Lorentz forces. These results support the view that the impulsive helicity transportation during the flare could be driven by the change in the Lorentz force applied on the photosphere., Comment: 14 pages, 6 figures, accepted for publication in ApJ