Approximation Limits of Linear Programs (Beyond Hierarchies)
Samuel Fiorini (Université Libre de Bruxelles)

We develop a framework for approximation limits of polynomial-size linear 
programs from lower bounds on the nonnegative ranks of suitably defined 
matrices. This framework yields unconditional impossibility results that are 
applicable to any linear program as opposed to only programs generated by 
hierarchies. Using our framework, we prove that O(n^{1/2-eps})-approximations 
for CLIQUE require linear programs of size 2^{n^\Omega(eps)}. (This lower bound 
applies to linear programs using a certain encoding of CLIQUE as a linear 
optimization problem.) Moreover, we establish a similar result for 
approximations of semidefinite programs by linear programs. Our main ingredient 
is a quantitative improvement of Razborov's rectangle corruption lemma for the 
high error regime, which gives strong lower bounds on the nonnegative rank of 
certain perturbations of the unique disjointness matrix.

This is joint work with Gábor Braun (Leipzig), Sebastian Pokutta (Erlangen),
David Steurer (Cornell)