Information Without Rolling Dice


Jacobs School of Engineering, Jacobs Hall, Room 2512

Sponsored By:
Professor Young-Han Kim

Massimo Franceschetti
Department of Electrical and Computer Engineering University of California, San Diego
Massimo Franceschetti


Can one revisit the main concepts of information theory in a deterministic setting? Shortly after Shannon’s work came about, this was the program set by the great Soviet mathematician Andrey Kolmogorov. In this talk, we review Kolmogorov’s program and cast his results in the context of square-integrable, band-limited signals subject to perturbation. For this class of signals, spectral concentration properties are well known, and closed form formulas can be obtained. We also introduce The (ε,δ)-capacity, that extends the Kolmogorov ε-capacity to packing sets in high dimensions, and compare it to the Shannon capacity. The functional form of the results indicates that in both Kolmogorov and Shannon's settings, capacity and entropy grow linearly with the number of degrees of freedom,but only logarithmically with the signal to noise ratio. This insight transcends the details of the stochastic or deterministic description of the information-theoretic model. For δ=0, results lead to new bounds on the Kolmogorov ε-capacity, and a tight asymptotic expression of the Kolmogorov ε-entropy of band-limited signals. Finally, we spend a few words on the generalization to signals of multiple variables, apt at modeling space-time fields.

This is joint work with Taehyung J. Lim.

Speaker Bio:
Massimo Franceschetti received the Laurea degree (with highest honors) in computer engineering from the University of Naples, Naples, Italy, in 1997, the M.S. and Ph.D. degrees in electrical engineering from the California Institute of Technology, Pasadena, CA, in 1999, and 2003, respectively. He is Professor of Electrical and Computer Engineering at the University of California at San Diego (UCSD). Before joining UCSD, he was a postdoctoral scholar at the University of California at Berkeley for two years. He has held visiting positions at the Vrije Universiteit Amsterdam, the École Polytechnique Fédérale de Lausanne, and the University of Trento. His research interests are in physical and information-based foundations of communication and control systems. He is co-author of the book ‘‘Random Networks for Communication’’ published by Cambridge University Press. Dr. Franceschetti served as Associate Editor for the IEEE Transactions on Information Theory (200 – 2012) and for the IEEE Transactions on Control of Network Systems (2013-16) as Guest Associate Editor of the IEEE Journal on Selected Areas in Communications (2008, 2009). He is currently serving as Associate Editor of the and the IEEE Transactions on Network Science and Engineering. He was awarded the C. H. Wilts Prize in 2003 for best doctoral thesis in electrical engineering at Caltech; the S.A. Schelkunoff Award in 2005 for best paper in the IEEE Transactions on Antennas and Propagation, a National Science Foundation (NSF) CAREER award in 2006, an Office of Naval Research (ONR) Young Investigator Award in 2007, the IEEE Communications Society Best Tutorial Paper Award in 2010, and the IEEE Control theory society Ruberti young researcher award in 2012.

Cheryle Wills,