On the Power of Symmetric Linear Programs
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.
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.
The talki is based on joint work with Albert Atserias and Anuj Dawar [1].
References
- [1]
- Albert Atserias, Anuj Dawar, and Joanna Ochremiak. On the power of symmetric linear programs. J. ACM, 68(4), jul 2021.
This document was translated from LATEX by HEVEA.