On the Power of Symmetric Linear Programs
- 29 July 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (4), 1-35
- https://doi.org/10.1145/3456297
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.Keywords
Funding Information
- European Research Council
- European Union's Horizon 2020 research and innovation programme (ERC-2014-CoG 648276)
- MICCIN (TIN2016-76573-C2-1P (TASSAT3))
- Alan Turing Institute under the EPSRC (EP/N510129/1)
- Marie Skłodowska-Curie (795936)
This publication has 28 references indexed in Scilit:
- PseudorandomnessFoundations and Trends® in Theoretical Computer Science, 2012
- From polynomial time queries to graph structure theoryCommunications of the ACM, 2011
- Affine systems of equations and counting infinitary logicTheoretical Computer Science, 2009
- Choiceless polynomial timeAnnals of Pure and Applied Logic, 1999
- A Restricted Second Order Logic for Finite StructuresInformation and Computation, 1998
- Expected complexity of graph partitioning problemsDiscrete Applied Mathematics, 1995
- Large Cliques Elude the Metropolis ProcessRandom Structures & Algorithms, 1992
- Expressing combinatorial optimization problems by Linear ProgramsJournal of Computer and System Sciences, 1991
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming ProblemsSIAM Journal on Discrete Mathematics, 1990
- Dynamic Programming Treatment of the Travelling Salesman ProblemJournal of the ACM, 1962