On the Power of Symmetric Linear Programs

DOI10.1145/3456297MaRDI QIDQ5056416zbMATH OpenOpenAlexFDO

Authors Albert Atserias, Anuj Dawar, Joanna Ochremiak

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.07825

zbMATH Keywords

extended formulationslinear programmingperfect matchingplanted cliquesymmetric group

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35)

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.

Recommendations

• Expressing combinatorial optimization problems by linear programs
• Symmetry matters for the sizes of extended formulations
• The matching problem has no small symmetric SDP
• The matching problem has no small symmetric SDP
• Linear vs. semidefinite extended formulations

Cited in

(13)

• Expressing combinatorial optimization problems by linear programs
• The matching problem has no small symmetric SDP
• Exponential lower bounds for polytopes in combinatorial optimization
• Average case polyhedral complexity of the maximum stable set problem
• Solving linear programs without breaking abstractions
• Average case polyhedral complexity of the maximum stable set problem
• The matching problem has no small symmetric SDP
• Representations of monotone Boolean functions by linear programs
• Separating LREC from LFP
• On the power of symmetric linear programs
• Orbit-finite linear programming
• Symmetric arithmetic circuits
• Limits of symmetric computation (invited talk)

This page was built for publication: On the Power of Symmetric Linear Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056416)