Princeton Science of Information Day

• Fri Sep 18, 2015: Agenda updated (Talk titles and abstracts added)
• Tue Sep 15, 2015: Agenda updated (Talk titles and abstracts added)
• Mon Sep 14, 2015: Agenda updated (Talk titles and abstracts added)
• Fri Sep 11, 2015: Agenda updated (Talk titles and abstracts added)
• Wed Sep 9, 2015: Minor Agenda updates, Intro paragraph updated, banner image updated
• Tue Sep 8, 2015: Agenda updated
• Fri Sep 4, 2015: Page created

Discussing two examples from the paper "Discrete Actions in Information-Constrained Decision Problems"

This talk will explore the relationship between Rate Distortion Theory and Rational Inattention Models. Rational Inattention Models, recently formulated and explored by Professor Chris Sims and others, introduce information processing into the rational actor's decision problem. This detail allows for an alternative formulation of economic decision problems where the actor can interact with his endowed beliefs. Rate Distortion Theory explores the dynamics of the transmission of information. In exploring the connection between these two theories, we can use the rich Rate Distortion Theory literature to better understand Rational Inattention and, in particular, give operational meaning to some of the mathematical objects used in Rational Inattention.

Basic theorems about quantum entropy will be reviewed with special emphasis on the differences between quantum and classical entropies. Classical and quantum versions of the uncertainty principle will also be discussed. (Partially joint work with Eric Carlen and Rupert Frank.)

We introduce the notion of entropic matroids over finite fields, give some equivalent descriptions, and show that they form a minor-closed class that coincides with linear matroids over fields of size 2 and 3, but not necessarily in general.

The stochastic block model has recently attracted major attention in the theoretical and practical study of community detection. We show that for this model, extracting communities has a fundamental limit, which we characterize in terms of an f-divergence. This defines a notion of clustering capacity analogous to Shannon’s channel capacity. We then develop an efficient algorithm that achieves the limit, implying that there is no computational barrier for community extraction. Joint work with Colin Sandon.

In this talk, we discuss the relationship between an information-theoretic property of codes (achieving capacity on an erasure channel) and a linear-algebraic property of matrices (having high probabilistic girth). Using this relationship, we describe new method for constructing codes that achieve capacity on erasure channels, and discuss how this method relates to polar codes.

In recent years, a number of results in different areas within computer science and information theory have critically utilized reverse hypercontractivity -​ an important notion from probability ​theory ​and functional analysis. In this work, we provide an equivalent description of this phenomenon using inequalities among information measures.

In a profoundly influential 1948 paper, Claude Shannon defined the entropy function H, and showed that the capacity of the eps-BSC, the binary symmetric channel with crossover probability eps, is 1-H(eps). This means that one can reliably communicate n bits by sending roughly n / (1-H(eps)) bits over this channel.

The extensive study of interactive communication protocols in the last decades gives rise to the related question of finding the capacity of the eps-BSC when it is used interactively. We define interactive channel capacity as the minimal ratio between the communication required to compute a function (over a noiseless channel), and the communication required to compute the same function over the eps-BSC. We show that the interactive channel capacity is roughly 1 - c * sqrt(H(eps)), for some constant c. Our result gives the first separation between interactive and non-interactive channel capacity.

Reed-Muller codes encode an m-variate polynomial of degree r by evaluating it on all points in {0,1}^m. Its distance is 2^{m-r} and so it cannot correct more than that many errors/erasures in the worst case. For random errors one may hope for a better result. In his seminal paper Shannon exactly determined the amount of errors and erasures one can hope to correct for codes of a given rate. Codes that achieve Shannon’s bound are called capacity achieving codes. In this talk we will show that Reed-Muller codes of low rate achieve capacity for both erasures and errors. We will also show that for high rate RM codes achieve capacity for erasures. Time permitting we will give an algorithm that for high rate RM codes corrects many more random errors than what minimal distance dictates.

Based on joint works with Emmanuel Abbe and Avi Wigderson and with Ramprasad saptharishi and Ben lee Volk.

In this talk, we show that a sequence of Reed-Muller codes with increasing length achieves capacity on the binary erasure channel if the sequence of rates converges. This possibility was first discussed by Dumer and Farrell in 1994 but has been settled so far only for some cases where the limiting code rate is 0 or 1. In fact, our primary technical result is quite general and also includes extended primitive narrow-sense BCH codes and all other affine-invariant codes. The method can be seen as a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes, this method requires only that the codes are highly symmetric. In particular, the technique applies to any sequence of linear codes where the block lengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. This also provides a rare example in information theory where symmetry alone implies near-optimal performance. The primary tools used in the proof are the sharp threshold property for symmetric monotone Boolean functions and the area theorem for extrinsic information transfer functions.

Henry D. Pfister received his Ph.D. in electrical engineering in 2003 from the University of California, San Diego and he is currently an associate professor in the electrical and computer engineering department of Duke University. Prior to that, he was a professor at Texas A&M University (2006-2014), a post-doctoral fellow at the École Polytechnique Fédérale de Lausanne (2005-2006), and a senior engineer at Qualcomm Corporate R&D in San Diego (2003-2004).

He received the NSF Career Award in 2008, the Texas A&M ECE Department Outstanding Professor Award in 2010, and was a coauthor of the 2007 IEEE COMSOC best paper in Signal Processing and Coding for Data Storage. He is currently an associate editor in coding theory for the IEEE Transactions on Information Theory (2013-2016) and a Distinguished Lecturer of the IEEE Information Theory Society (2015-2016).

In 1975, Wyner published two very different papers that are unexpectedly connected. One introduced the wiretap channel, showing that information-theoretic secrecy is possible without a secret key by taking advantage of channel noise. This is the foundation for much of physical-layer security. The other paper introduced a notion of common information relevant to generating random variables at different terminals. In that work he introduced a soft-covering tool for proving achievability. Coincidently, soft-covering (a.k.a. resolvability) has now become the tool of choice for proving strong secrecy in settings such as wiretap channels, although Wyner didn't appear to make any connection between the two results.

We present a sharpening of the soft-covering tool by showing that the soft-covering phenomenon happens with doubly-exponential certainty with respect to a randomly generated codebook. Through the union bound, this enables security proofs in settings where many security constraints must be satisfied simultaneously. The type II wiretap channel is a great example of this, where the eavesdropper can choose at which times to make observations. We demonstrate the effectiveness of this tool by deriving the secrecy capacity of wiretap channels of type II with a noisy main channel---previously an open problem. Additionally, this stronger soft-covering allows information-theoretic security proofs using soft-covering to be easily upgraded to semantic security, which is a gold standard in cryptography.

Rate-Distortion Theory is a branch of Information Theory which provides theoretical foundation for lossy data compression. In this setting, the decompressed data need not match original data exactly; however, it must be reconstructed with a prescribed fidelity which is given by some distortion measure. An endemic assumption in information theory is that the given distortion measures are separable: that is, the distortion function can be written as an arithmetic average of per-letter distortions. This set up gives nice theoretical results at the expense of a very restrictive model; real-world distortion functions rarely have such nice structure.

Motivated by works of Kolmogorov and Nagumo on generalized notions of mean we introduce f-separable distortion measures. This generalization allows for the analysis of a much wider class of distortion measures than those which have received the bulk of attention in literature. We derive the rate-distortion function for discrete memoryless sources and f-separable distortion measures, as well as present some illuminating examples of different f-separable distortion measures.

Recently among the information theory community, there is a growing interest in functional inequalities such as hypercontractivity, strong data processing inequality and the logarithmic probability comparison bounds, and their utility in the proof of coding theorems. In a unified way, we show that these inequalities have equivalent information-theoretic formulations, by generalizing a theorem of Carlen and Cordero-Erausquin on the duality of Brascamp-Lieb type inequality and the subadditivity of entropy. The information-theoretic formulations are more convenient for proving certain properties such as data processing, tensorization, convexity (Riesz-Thorin interpolation) and Gaussian optimality (using Geng-Nair's approach), partly because of the tool of chain rules associated with the information measures. On the other hand, the functional formulations allow us to prove strong converses or zero-rate converses of certain coding theorems, which strengthens the traditional weak converses obtained through manipulations of information-theoretic formulas and Fano's inequality (joint work with Thomas Courtade, Paul Cuff and Sergio Verdú).