Abstract
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 various distance estimations we can bound the extension complexity of various polytopes of interest.