Information Theory and Polyhedral Combinatorics
summary
Describes a concrete pipeline that lowers bounds on LP sizes by turning an optimization problem into its slack matrix, interpreting that matrix as a distribution and bounding its nonnegative rank via an information measure called common information. Uses Hellinger-distance cut‑and‑paste identities and a direct‑sum condition to reduce to many constant‑size subproblems. Delivers exponential extension‑complexity lower bounds for the correlation polytope and shows matching LPs and many approximations still need exponentially many inequalities, so the method succeeds.
AI-written summary · about