Approximability and proof complexity

Ryan O'Donnell, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This work is concerned with the proof-complexity of certifying that optimization problems do not have good solutions. Specifically we consider bounded-degree "Sum of Squares" (SOS) proofs, a powerful algebraic proof system introduced in 1999 by Grigoriev and Vorobjov. Work of Shor, Lasserre, and Parrilo shows that this proof is automatizable using semidefinite programming (SDP), meaning that any n-variable degree-d proof can be found in time nO(d). Furthermore, the SDP is dual to the well-known Lasserre SDP hierarchy, meaning that the "d/2-round Lasserre value" of an optimization problem is equal to the best bound provable using a degree-d SOS proof. These ideas were exploited in a recent paper by Barak et al. (STOC 2012) which shows that the known "hard instances" for the Unique-Games problem are in fact optimally solved by a constant level of the Lasserre SDP hierarchy. We continue the study of the power of SOS proofs in the context of difficult optimization problems. In particular, we show that the Balanced-Separator integrality gap instances proposed by Devanur et al. can have their optimal value certified by a degree-4 SOS proof. The key ingredient is an SOS proof of the KKL Theorem. We also investigate the extent to which the Khot-Vishnoi Max-Cut integrality gap instances can have their optimum value certified by an SOS proof. We show they can be certified to within a factor .952 (> .878) using a constant-degree proof. These investigations also raise an interesting mathematical question: is there a constant-degree SOS proof of the Central Limit Theorem?

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Pages1537-1556
Number of pages20
StatePublished - Apr 16 2013
Externally publishedYes
Event24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 - New Orleans, LA, United States
Duration: Jan 6 2013Jan 8 2013

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
CountryUnited States
CityNew Orleans, LA
Period1/6/131/8/13

Fingerprint

Proof Complexity
Approximability
Sum of squares
Semidefinite Programming
Separators
Degree Sum
Integrality
Optimization Problem
Max-cut
Separator
Proof System
Central limit theorem
Continue

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

O'Donnell, R., & Zhou, Y. (2013). Approximability and proof complexity. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 (pp. 1537-1556). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Approximability and proof complexity. / O'Donnell, Ryan; Zhou, Yuan.

Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. 2013. p. 1537-1556 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

O'Donnell, R & Zhou, Y 2013, Approximability and proof complexity. in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1537-1556, 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, LA, United States, 1/6/13.
O'Donnell R, Zhou Y. Approximability and proof complexity. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. 2013. p. 1537-1556. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
O'Donnell, Ryan ; Zhou, Yuan. / Approximability and proof complexity. Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. 2013. pp. 1537-1556 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
@inproceedings{c7dc48b4fc0546e084edb34e9898d32b,
title = "Approximability and proof complexity",
abstract = "This work is concerned with the proof-complexity of certifying that optimization problems do not have good solutions. Specifically we consider bounded-degree {"}Sum of Squares{"} (SOS) proofs, a powerful algebraic proof system introduced in 1999 by Grigoriev and Vorobjov. Work of Shor, Lasserre, and Parrilo shows that this proof is automatizable using semidefinite programming (SDP), meaning that any n-variable degree-d proof can be found in time nO(d). Furthermore, the SDP is dual to the well-known Lasserre SDP hierarchy, meaning that the {"}d/2-round Lasserre value{"} of an optimization problem is equal to the best bound provable using a degree-d SOS proof. These ideas were exploited in a recent paper by Barak et al. (STOC 2012) which shows that the known {"}hard instances{"} for the Unique-Games problem are in fact optimally solved by a constant level of the Lasserre SDP hierarchy. We continue the study of the power of SOS proofs in the context of difficult optimization problems. In particular, we show that the Balanced-Separator integrality gap instances proposed by Devanur et al. can have their optimal value certified by a degree-4 SOS proof. The key ingredient is an SOS proof of the KKL Theorem. We also investigate the extent to which the Khot-Vishnoi Max-Cut integrality gap instances can have their optimum value certified by an SOS proof. We show they can be certified to within a factor .952 (> .878) using a constant-degree proof. These investigations also raise an interesting mathematical question: is there a constant-degree SOS proof of the Central Limit Theorem?",
author = "Ryan O'Donnell and Yuan Zhou",
year = "2013",
month = "4",
day = "16",
language = "English (US)",
isbn = "9781611972511",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
pages = "1537--1556",
booktitle = "Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013",

}

TY - GEN

T1 - Approximability and proof complexity

AU - O'Donnell, Ryan

AU - Zhou, Yuan

PY - 2013/4/16

Y1 - 2013/4/16

N2 - This work is concerned with the proof-complexity of certifying that optimization problems do not have good solutions. Specifically we consider bounded-degree "Sum of Squares" (SOS) proofs, a powerful algebraic proof system introduced in 1999 by Grigoriev and Vorobjov. Work of Shor, Lasserre, and Parrilo shows that this proof is automatizable using semidefinite programming (SDP), meaning that any n-variable degree-d proof can be found in time nO(d). Furthermore, the SDP is dual to the well-known Lasserre SDP hierarchy, meaning that the "d/2-round Lasserre value" of an optimization problem is equal to the best bound provable using a degree-d SOS proof. These ideas were exploited in a recent paper by Barak et al. (STOC 2012) which shows that the known "hard instances" for the Unique-Games problem are in fact optimally solved by a constant level of the Lasserre SDP hierarchy. We continue the study of the power of SOS proofs in the context of difficult optimization problems. In particular, we show that the Balanced-Separator integrality gap instances proposed by Devanur et al. can have their optimal value certified by a degree-4 SOS proof. The key ingredient is an SOS proof of the KKL Theorem. We also investigate the extent to which the Khot-Vishnoi Max-Cut integrality gap instances can have their optimum value certified by an SOS proof. We show they can be certified to within a factor .952 (> .878) using a constant-degree proof. These investigations also raise an interesting mathematical question: is there a constant-degree SOS proof of the Central Limit Theorem?

AB - This work is concerned with the proof-complexity of certifying that optimization problems do not have good solutions. Specifically we consider bounded-degree "Sum of Squares" (SOS) proofs, a powerful algebraic proof system introduced in 1999 by Grigoriev and Vorobjov. Work of Shor, Lasserre, and Parrilo shows that this proof is automatizable using semidefinite programming (SDP), meaning that any n-variable degree-d proof can be found in time nO(d). Furthermore, the SDP is dual to the well-known Lasserre SDP hierarchy, meaning that the "d/2-round Lasserre value" of an optimization problem is equal to the best bound provable using a degree-d SOS proof. These ideas were exploited in a recent paper by Barak et al. (STOC 2012) which shows that the known "hard instances" for the Unique-Games problem are in fact optimally solved by a constant level of the Lasserre SDP hierarchy. We continue the study of the power of SOS proofs in the context of difficult optimization problems. In particular, we show that the Balanced-Separator integrality gap instances proposed by Devanur et al. can have their optimal value certified by a degree-4 SOS proof. The key ingredient is an SOS proof of the KKL Theorem. We also investigate the extent to which the Khot-Vishnoi Max-Cut integrality gap instances can have their optimum value certified by an SOS proof. We show they can be certified to within a factor .952 (> .878) using a constant-degree proof. These investigations also raise an interesting mathematical question: is there a constant-degree SOS proof of the Central Limit Theorem?

UR - http://www.scopus.com/inward/record.url?scp=84876025683&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84876025683&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84876025683

SN - 9781611972511

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1537

EP - 1556

BT - Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

ER -