|
Title:
|
Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem
|
|
Author:
|
Atserias, Albert; Ochremiak, Joanna
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
|
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 graph 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. © 2018 ACM. |
|
Abstract:
|
Peer Reviewed |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
-Computational complexity
-Linear programming
-Ellipsoid method
-Fixed-point logic
-Graph isomorphism problem
-Semidefinite programming
-Sums-of-squares
-Set theory
-Computer circuits
-Complexitat computacional
-Programació lineal |
|
Rights:
|
|
|
Document type:
|
Article - Submitted version
Conference Object |
|
Published by:
|
Association for Computing Machinery (ACM)
|
|
Share:
|
|
