Allerton 2015 Paper Abstract


Paper ThC2.2

Pokutta, Sebastian (Georgia Institute of Technology)

Information Theory and Polyhedral Combinatorics

Scheduled for presentation during the Invited Session "Recent Developments in Information Theory, Statistics and Probability I" (ThC2), Thursday, October 1, 2015, 13:50−14:10, Solarium

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on December 5, 2021

Keywords Information Theory, Optimization, Coding Theory


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 an overview of information-theoretic techniques in the context of polyhedral combinatorics and extended formulations. We show how to establish 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 various distance estimations we can bound the extension complexity of important combinatorial problems.



All Content © PaperCept, Inc..

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2021 PaperCept, Inc.
Page generated 2021-12-05  10:22:14 PST  Terms of use