Spring 2015

Information Theory and Additive Combinatorics

Thursday, April 23rd, 2015 11:45 am12:15 pm

Add to Calendar

Additive number theory contains a number of so-called "sumset inequalities" that relate the cardinalities of various finite subsets of an abelian group G, for instance, the sumset A+A and the difference set A-A of a finite subset A of G. We explore probabilistic analogues of such results, showing for instance that for independent, identically distributed random variables X and X’ that are discrete and take values in an abelian group G, the entropies of X+X' and X-X' strongly constrain each other. We also discuss statements analogous to the entropy power inequality (which is well known for R^n) that can be made for specific discrete groups of interest such as the integers and finite cyclic groups. Some of our results have extensions to general locally compact abelian groups, and applications to probability theory, combinatorics, information theory, and convex geometry. Based on (multiple) joint works with Ioannis Kontoyiannis (Athens), Jiange Li (Delaware), Liyao Wang (Yale), and Jaeoh Woo (Yale).