research-article

Open access

Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem

Authors:

Albert Atserias,

Joanna OchremiakAuthors Info & Claims

LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science

Pages 66 - 75

https://doi.org/10.1145/3209108.3209186

Published: 09 July 2018 Publication History

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.

References

[1]

E. Allender, P. Bürgisser, J. Kjeldgaard-Pedersen, and P. B. Miltersen. 2009. On the Complexity of Numerical Analysis. SIAM J. Comput. 38, 5 (2009), 1987--2006.

Digital Library

[2]

M. Anderson, A. Dawar, and B. Holm. 2015. Solving Linear Programs Without Breaking Abstractions. J. ACM 62, 6 (2015), 48:1--48:26.

Digital Library

[3]

A. Atserias and E. Maneva. 2013. Sherali--Adams Relaxations and Indistinguishability in Counting Logics. SIAM J. Comput 42, 1 (2013), 112--137.

Digital Library

[4]

C. Berkholz. 2017. The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs. ECCC (2017).

[5]

C. Berkholz and M. Grohe. 2015. Limitations of Algebraic Approaches to Graph Isomorphism Testing. In ICALP. 155--166.

[6]

A. Blass, Y. Gurevich, and S. Shelah. 2002. On polynomial time computation over unordered structures. J. Symbolic Logic 67, 3 (2002), 1093--1125.

[7]

A. Dawar and P. Wang. 2017. Definability of semidefinite programming and Lasserre lower bounds for CSPs. In LICS. 1--12.

[8]

E. Grädel, M. Grohe, B. Pago, and W. Pakusa. 2018. A Finite-Model-Theoretic View on Propositional Proof Complexity. CoRR abs/1802.09377 (2018).

[9]

M. Grötschel, L. Lovász, and A. Schrijver. 1993. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag.

[10]

C. Josz and Didier Henrion. 2016. Strong duality in Lasserre's hierarchy for polynomial optimization. Optimization Letters 10, 1 (2016), 3--10.

[11]

J. B. Lasserre. 2001. Global Optimization with Polynomials and the Problems of Moments. SIAM Journal on Optimization 11, 3 (2001), 796--817.

Digital Library

[12]

P. N. Malkin. 2014. Sherali--Adams relaxations of graph isomorphism polytopes. Discrete Optimization 12 (2014), 73--97.

[13]

R. O'Donnell, J. Wright, C. Wu, and Y. Zhou. 2014. Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs. In SODA. 1659--1677.

Digital Library

[14]

M. Otto. 1997. Bounded variable logics and counting -- A study in finite models. Vol. 9. Springer-Verlag.

[15]

H. D. Sherali and W. P. Adams. 1990. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3, 3 (1990), 411--430.

Digital Library

[16]

S. P. Tarasov and M. N. Vyalyi. 2008. Semidefinite programming and arithmetic circuit evaluation. Discrete Appl. Math. 156, 11 (2008), 2070--2078.

Digital Library

[17]

G. Tinhofer. 1986. Graph isomorphism and theorems of Birkhoff type. Computing 36, 4 (1986), 285--300.

Digital Library

Cited By

Torán JWörz F(2024)Cutting Planes Width and the Complexity of Graph Isomorphism RefutationsACM Transactions on Computational Logic10.1145/367712125:4(1-25)Online publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1145/3677121
van Bergerem SGrohe MKiefer SOeljeklaus L(2023)Simulating Logspace-Recursion with Logarithmic Quantifier Depth2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS56636.2023.10175818(1-13)Online publication date: 26-Jun-2023
https://doi.org/10.1109/LICS56636.2023.10175818
Grohe MLichter MNeuen DSchweitzer P(2023)Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00052(798-809)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00052
Show More Cited By

Index Terms

Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem
1. Theory of computation

Recommendations

Tight Size-Degree Bounds for Sums-of-Squares Proofs

We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size $${n^{\Omega{(d)}}}$$nΩ(d) for values of d = d(n) from constant all the way up to $...
Tight size-degree bounds for sums-of-squares proofs
CCC '15: Proceedings of the 30th Conference on Computational Complexity

We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size n^Ω(d) for values of d = d(n) from constant all the way up to n^δ for some universal ...
An Exact Duality Theory for Semidefinite Programming Based on Sums of Squares

Farkas' lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science

July 2018

960 pages

ISBN:9781450355834

DOI:10.1145/3209108

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGLOG: ACM Special Interest Group on Logic and Computation
EACSL: European Association for Computer Science Logic
IEEE-CS\DATC: IEEE Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Conference

LICS '18

Sponsor:

SIGLOG
EACSL
IEEE-CS\DATC

LICS '18: 33rd Annual ACM/IEEE Symposium on Logic in Computer Science

July 9 - 12, 2018

Oxford, United Kingdom

Acceptance Rates

Overall Acceptance Rate 215 of 622 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
438
Total Downloads

Downloads (Last 12 months)90
Downloads (Last 6 weeks)16

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Torán JWörz F(2024)Cutting Planes Width and the Complexity of Graph Isomorphism RefutationsACM Transactions on Computational Logic10.1145/367712125:4(1-25)Online publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1145/3677121
van Bergerem SGrohe MKiefer SOeljeklaus L(2023)Simulating Logspace-Recursion with Logarithmic Quantifier Depth2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS56636.2023.10175818(1-13)Online publication date: 26-Jun-2023
https://doi.org/10.1109/LICS56636.2023.10175818
Grohe MLichter MNeuen DSchweitzer P(2023)Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00052(798-809)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00052
Borowska-Stefańska MKowalski MKurzyk PSahebgharani AWiśniewski S(2022)Spatiotemporal Changeability of the Load of the Urban Road Transport System under Permanent and Short-Term Legal and Administrative Retail RestrictionsSustainability10.3390/su1409513714:9(5137)Online publication date: 24-Apr-2022
https://doi.org/10.3390/su14095137
Grohe MSchweitzer PWiebking DMarx D(2021)Deep weisfeiler lemanProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458218(2600-2614)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458218
Grohe MHermanns HZhang LKobayashi NMiller D(2020)Counting Bounded Tree Depth HomomorphismsProceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3373718.3394739(507-520)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3373718.3394739
Atserias ADawar A(2019)Definable inapproximability: new challenges for duplicatorJournal of Logic and Computation10.1093/logcom/exz02229:8(1185-1210)Online publication date: 2-Dec-2019
https://doi.org/10.1093/logcom/exz022
Krajíček J(2019)Proof Complexity10.1017/9781108242066Online publication date: 25-Mar-2019
https://doi.org/10.1017/9781108242066

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten