Common information was introduced by Wyner as a measure of dependence of two
random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix. Lower bounds on nonnegative rank have important applications to several areas such
as communication ... more >>>

We prove that any extended formulation that approximates the matching polytope on n-vertex graphs up to a factor of (1+\varepsilon) for any \frac2n \le \varepsilon \le 1 must have at least {n}\choose{{\alpha}/{\varepsilon}} defining inequalities where 0<\alpha<1 is an absolute constant. This is tight as exhibited by the (1+\varepsilon) approximating linear ... more >>>