Information Theory and Polyhedral Combinatorics

Professor Sebastian Pokutta
Assistant Professor, Georgia Institute of Technology
Given on: Oct. 23rd, 2014
Venue: Packard 101
Time: 4:15pm to 5:15pm


Information theory is a powerful tool to analyze the behavior of communication systems. However, its applicability goes far beyond this and more recently many important problems in Theoretical Computer Science as well as Optimization have been addressed by means of Information Theory. We provide a new framework for establishing strong lower bounds on the nonnegative rank of matrices by means of common information, a notion previously introduced in Wyner 1975. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance estimations we can compute the (almost) exact common information of UDISJ partial matrix, a special matrix that is of high interest in communication complexity and extended formulations.


Sebastian Pokutta's research concentrates on combinatorial optimization, polyhedral combinatoris, and information theory, and in particular focuses on cutting-plane methods and extended formulations. These methods are essential to solving large-scale optimization problems with combinatorial aspects as they allow for recovering crucial information on the structure of optimal solutions. His applied research focuses on application of operations research and optimization methods to problems in supply chain managment, production planning, mechanical engineering, and finance. Sebastian Pokutta’s applied work focuses on the combination of optimization methods with state-of-the-art techniques from information theory with applications in the broader field of engineering. He is an Assistant Professor in the School of Industrial and Systems Engineering at Georgia Tech. He received both his diploma and Ph.D. in mathematics from the University of Duisburg-Essen in Germany. He was a postdoctoral researcher and visiting lecturer at MIT, worked for IBM ILOG and Krall Demmel Baumgarten. Prior to joining Georgia Tech, we was an Assistant Professor at the University of Erlangen-Nürnberg. He received the Coca-Cola Early Career Assistant Professorship in 2014.