Title: On the Power of Symmetric Linear Programs,
Abstract: We consider families of symmetric linear programs (LPs) that decide a
property of graphs (or other relational structures) in the sense that, for each
size of graph, there is an LP defining a polyhedral lift that separates the
integer points corresponding to graphs with the property from those
corresponding to graphs without the property. We show that this is equivalent,
with at most polynomial blow-up in size, to families of symmetric Boolean
circuits with threshold gates. In particular, when we consider polynomial-size
LPs, the model is equivalent to definability in a non-uniform version of
fixed-point logic with counting (FPC). Known upper and lower bounds for FPC
apply to the non-uniform version. In particular, this implies that the class of
graphs with perfect matchings has polynomial-size symmetric LPs while we obtain
an exponential lower bound for symmetric LPs for the class of Hamiltonian
graphs. We compare and contrast this with previous results (Yannakakis 1991)
showing that any symmetric LPs for the matching and TSP polytopes have
exponential size. As an application, we establish that for random, uniformly
distributed graphs, polynomial-size symmetric LPs are as powerful as general
Boolean circuits. We illustrate the effect of this on the well-studied
planted-clique problem.