Lei Yu

Dr. Lei Yu

orcid

Research Focus & Metrics

Academic Career Length

11Years (2016-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
28 April 2022 in Foundations and Trends® in Communications and Information Theory
Verified
Journal Article
Closed access
PDF file
LYLei Yu
Lei Yu
VTVincent Tan
Vincent Tan
Common information is ubiquitous in information theory and related areas such as theoretical computer science and discrete probability. However, because there are multiple notions of common information, a unified understanding of the deep interconnections between them is lacking. This monograph seeks to fill this gap by leveraging a small set of mathematical techniques that are applicable across seemingly disparate problems. In Part I, we review the operational tasks and properties associated with Wyner’s and Gács–Körner–Witsenhausen’s (GKW’s) common information. In Part II, we discuss extensions of the former from the perspective of distributed source simulation. This includes the Rènyi common information which forms a bridge between Wyner’s common information and the exact common information. Via a surprising equivalence between the Rènyi common information of order ∞ and the exact common information, we demonstrate the existence of a joint source in which the exact common information strictly exceeds Wyner’s common information. Other closely related topics discussed in Part II include the channel synthesis problem and the connection of Wyner’s and exact common information to the nonnegative rank of matrices. In Part III, recognizing that GKW’s common information is zero for most non-degenerate sources, we examine it with a more refined lens via the Non-Interactive Correlation Distillation (NICD) problem in which we quantify the agreement probability of extracted bits from a bivariate source. We extend this to the noise stability problem which includes as special cases the k-user NICD and q-stability problems. This allows us to seamlessly transition to discussing their connections to various conjectures in information theory and discrete probability, such as the Courtade–Kumar, Li–Mèdard and Mossell–O’Donnell conjectures. Finally, we consider functional inequalities (e.g., the hypercontractivity and Brascamp–Lieb inequalities), which constitute a further generalization of the noise stability problem in which the Boolean functions therein are replaced by nonnnegative functions. We demonstrate that the key ideas behind the proofs in Part III can be presented in a pedagogically coherent manner and unified via information-theoretic and Fourier-analytic methods.

6 December 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
LYLei Yu
Lei Yu
VTVincent Tan
Vincent Tan
The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in [0,2] ∪ {∞}) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to 1 as well as (lower and upper) bounds for the case when the same parameter is smaller than 1. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than 1, consistent with the traditional case where the Rényi parameter is equal to 1, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 1 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d. random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence. This tradeoff differs from the conventional setting when the leakage is measured by the traditional mutual information.

20 July 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
LYLei Yu
Lei Yu
VTVincent Tan
Vincent Tan
A coupling of two distributions PX and PY is a joint distribution PXY with marginal distributions equal to PX and PY . Given marginals PX and PY and a real-valued function f of the joint distribution PXY , what is its minimum over all couplings PXY of PX and PY ? We study the asymptotics of such coupling problems with different f’s and with X and Y replaced by Xn = (X1, … ,Xn) and Y n = (Y1, … , Yn) where Xi and Yi are i.i.d. copies of random variables X and Y with distributions PX and PY respectively. These include the maximal coupling, minimum distance coupling, maximal guessing coupling, and minimum entropy coupling problems. We characterize the limiting values of these coupling problems as n tends to infinity. We show that they typically converge at least exponentially fast to their limits. Moreover, for the problems of maximal coupling and minimum excess-distance probability coupling, we also characterize (or bound) the optimal convergence rates (exponents). Furthermore, for the maximal guessing coupling problem we show that it is equivalent to the distribution approximation problem. Therefore, some existing results for the latter problem can be used to derive the asymptotics of the maximal guessing coupling problem. We also study the asymptotics of the maximal guessing coupling problem for two general sources and a generalization of this problem, named the maximal guessing coupling through a channel problem. We apply the preceding results to several new informationtheoretic problems, including exact intrinsic randomness, exact resolvability, channel capacity with input distribution constraint, and perfect stealth and secrecy communication.

30 September 2019 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
LYLei Yu
Lei Yu
VTVincent Tan
Vincent Tan
We consider the exact channel synthesis problem. This problem concerns the determination of the minimum amount of information required to create exact correlation remotely when there is a certain rate of randomness shared by two terminals. This problem generalizes an existing approximate version, in which the generated joint distribution is required to be close to a target distribution under the total variation (TV) distance measure (instead being exactly equal to the target distribution). We provide single-letter inner and outer bounds on the admissible region of the shared randomness rate and the communication rate for the exact channel synthesis problem. These two bounds coincide for doubly symmetric binary sources. We observe that for such sources, the admissible rate region for exact channel synthesis is strictly included in that for the TV-approximate version. We also extend the exact and TV-approximate channel synthesis problems to sources with countably infinite alphabets and continuous sources; the latter includes Gaussian sources. As by-products, lemmas concerning soft-covering under Rényi divergence measures are derived.

8 May 2023 in Entropy
Verified
Journal Article
Open access
PDF file
LYLei Yu
Lei Yu
The union-closed sets conjecture states that, in any nonempty union-closed family F of subsets of a finite set, there exists an element contained in at least a proportion 1/2 of the sets of F. Using an information-theoretic method, Gilmer recently showed that there exists an element contained in at least a proportion 0.01 of the sets of such F. He conjectured that their technique can be pushed to the constant 3−52 which was subsequently confirmed by several researchers including Sawin. Furthermore, Sawin also showed that Gilmer’s technique can be improved to obtain a bound better than 3−52 but this new bound was not explicitly given by Sawin. This paper further improves Gilmer’s technique to derive new bounds in the optimization form for the union-closed sets conjecture. These bounds include Sawin’s improvement as a special case. By providing cardinality bounds on auxiliary random variables, we make Sawin’s improvement computable and then evaluate it numerically, which yields a bound approximately 0.38234, slightly better than 3−52≈0.38197.

1 June 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
LZLin Zhou
Lin Zhou
VTVincent Tan
Vincent Tan
LYLei Yu
Lei Yu
Mehul MotaniMehul Motani
Mehul Motani
We revisit the high-dimensional content identification with lossy recovery problem (Tuncel and Gündüz, 2014) and establish an exponential strong converse theorem. As a corollary of the exponential strong converse theorem, we derive an upper bound on the joint identification-error and excess-distortion exponent for the problem. Our main results can be specialized to the biometrical identification problem (Willems, 2003) and the content identification problem (Tuncel, 2009) since these two problems are both special cases of the content identification with lossy recovery problem. We leverage the information spectrum method introduced by Oohama and adapt the strong converse techniques therein to be applicable to the problem at hand.