Definable ellipsoid method, sums-of-squares proofs, and the graph isomorphism problem
SIAM JOURNAL ON COMPUTING(2023)
摘要
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 further 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.
更多查看译文
关键词
ellipsoid method,fixed-point logic,semidefinite programming,sums-of-squares,graph isomorphism problem
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要