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

DOI10.1145/3209108.3209186zbMATH Open1452.90238arXiv1802.02388OpenAlexW2964147799MaRDI QIDQ5145277FDOQ5145277

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)

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.

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

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

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)

Cited In (4)

• Title not available (Why is that?)
• Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
• Cutting planes width and the complexity of graph isomorphism refutations
• Definable Inapproximability: New Challenges for Duplicator

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)