## Exact Soft Covering ExponentPaul Cuff ## AbstractSoft covering is a phenomenon whereby an i.i.d. distribution on sequences of a given length is approximately produced from a very structured generation process. Specifically, a sequence is drawn uniformly at random from a "codebook" of sequences and then corrupted by memoryless noise (i.e. a discrete memoryless channel, or DMC). Among other things, soft covering means that the codebook is not recognizable in the resulting distribution. The soft covering phenomenon occurs when the codebook itself is constructed randomly, with a correspondence between the codebook distribution, the DMC, and the target i.i.d. distribution, and when the codebook is large enough. Mutual information is the minimum exponential rate for the codebook size. We show the exact exponential rate of convergence of the approximating distribution to the target, as measured by total variation distance, as a function of the excess codebook rate above mutual information. The proof involves a novel Poisson approximation step in the converse. Soft covering is a crucial tool for secrecy capacity proofs and has applications broadly in network information theory for analysis of encoder performance. Wyner invented this tool for the purpose of solving a problem he named "common information." The quantum analogue of Wyner's problem is "entanglement of purification," which is an important open problem with physical significance: What is the minimum entanglement needed to produce a desired quantum state spanning two locations? The literature on this problem identifies sufficient asymptotic rates for this question that are generally excessively high. I will make brief mention of how the soft covering principle might be utilized for a more efficient design in this quantum setting. ## BioPaul Cuff was an assistant professor at Princeton University until 2017. He is now a principle researcher at Renaissance Technologies. The focus of Dr. Cuff's academic research has been information theory with an emphasis on secure communications, both data compression and channel capacity. He also taught the first and only graduate course on quantum information theory at Princeton. Additionally, he has dabbled with machine learning and signal processing, both in industry and academia. His Ph.D. advisor was Thomas Cover, and during that time as a student he was awarded the ISIT Best Student Paper Award. As an assistant professor at Princeton, Dr. Cuff received the NSF Career Award and the AFOSR Young Investigator Award, as well as awards for teaching and for papers with his students. |