Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem

DOI10.1145/3209108.3209186MaRDI QIDQ5145277zbMATH OpenOpenAlexFDO

Authors Albert Atserias, Joanna Ochremiak

Publication date 20 January 2021

Published in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingellipsoid methodfixed-point logicgraph isomorphism problemsums-of-squares

Mathematics Subject Classification ID

Semidefinite programming (90C22) Model theory of finite structures (03C13) Complexity of proofs (03F20)

Abstract: The ellipsoid method is an algorithm that solves the (weak) feasibility and linear optimization problems for convex sets by making oracle calls to their (weak) separation problem. We observe that the previously known method for showing that this reduction can be done in fixed-point logic with counting (FPC) for linear and semidefinite programs applies to any family of explicitly bounded convex sets. We use this observation to show that the exact feasibility problem for semidefinite programs is expressible in the infinitary version of FPC. As a corollary we get that, for the isomorphism problem, the Lasserre/Sums-of-Squares semidefinite programming hierarchy of relaxations collapses to the Sherali-Adams linear programming hierarchy, up to a small loss in the degree.

Recommendations

• Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
• Definability of semidefinite programming and Lasserre lower bounds for CSPs
• Solving linear programs without breaking abstractions
• Lower bounds on the size of semidefinite programming relaxations
• A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation

Cited in

(6)

• Solving linear programs without breaking abstractions
• Definable Inapproximability: New Challenges for Duplicator
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• Cutting planes width and the complexity of graph isomorphism refutations
• Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
• Definability of semidefinite programming and Lasserre lower bounds for CSPs

This page was built for publication: Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem

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