Skip to content

Extended Formulations and Information Theory

PokuttaDr. Sebastian Pokutta
Assistant Professor
Industrial and Systems Engineering at Georgia Tech
November 1, 2013, 2:30 PM – 3:30 PM
500 John D. Tickle Engineering Building

Dr. Sebastian Pokutta’s research concentrates on combinatorial optimization, polyhedral combinatorics, 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 management, 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. Dr. Sebastian Pokutta is an Assistant Professor in the Industrial and Systems Engineering department at Georgia Tech. He received both his master’s degree and Ph.D. in mathematics from the University of Duisburg-Essen in Germany. Subsequent to his graduate studies he worked as a postdoctoral fellow at the MIT Operations Research Center where the topic of his research was combinatorial optimization and cutting plane procedures. Upon completion of his postdoctoral fellowship at MIT Sebastian Pokutta was appointed as an optimization specialist at ILOG where he worked on production planning and supply chain optimization within the steel industry, automotive industry, and energy industry. In early 2008, he joined KDB (Krall Demmel Baumgarten), a state-of-the art risk management practice, and developed risk management methodologies at top tier banks. Prior to joining MIT as a visiting lecturer in Fall 2010, Sebastian Pokutta held the position of a research scientist at the Technische Universität Darmstadt.

Talk Abstract: Communication complexity and information theoretic approaches have been at the core of many recent lower bounds for extended formulations. A key problem is unique disjointness which is closely related to the extension complexity of the correlation polytope and the clique problem. We provide a new information-theoretic framework for lower bounding the nonnegative rank. Within this framework we present an (almost) optimal estimation of the nonnegative rank of the unique disjointness matrix.

(This is joint work with Gábor Braun)

The flagship campus of the University of Tennessee System and partner in the Tennessee Transfer Pathway.