Tight size-degree bounds for sums-of-squares proofs

DOI10.1007/s00037-017-0152-4zbMath1422.03125arXiv1504.01656OpenAlexW2606812758WikidataQ61732574 ScholiaQ61732574MaRDI QIDQ1686838

Jakob Nordström, Massimo Lauria

Publication date: 18 December 2017

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingsizedegreeranklower boundcliqueresolutionPositivstellensatzproof complexitysums-of-squaresLasserre

Mathematics Subject Classification ID

Semidefinite programming (90C22) Complexity of proofs (03F20)

Related Items (3)

Unnamed Item ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ MaxSAT Resolution and Subcube Sums

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relativization makes contradictions harder for resolution
• Combinatorics of first order structures and propositional proof systems
• The complexity of proving that a graph is Ramsey
• Anneaux preordonnes
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász–Schrijver Procedures
• Parameterized Bounded-Depth Frege Is not Optimal
• Relativisation Provides Natural Separations for Resolution-Based Proof Systems
• Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
• On the power of unique 2-prover 1-round games
• Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies
• An approach to obtaining global extremums in polynomial mathematical programming problems
• Interactive proofs and the hardness of approximating cliques
• Sum-of-squares proofs and the quest toward optimal algorithms
• SOS Is Not Obviously Automatizable, Even Approximately
• CSP gaps and reductions in the lasserre hierarchy
• Communication lower bounds via critical block sensitivity
• Narrow Proofs May Be Maximally Long
• Computer Science Logic
• Hypercontractivity, sum-of-squares proofs, and their applications
• LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE
• Approximability and proof complexity
• Parameterized Complexity of DPLL Search Procedures
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Complexity of Positivstellensatz proofs for the knapsack
• Complexity of Null- and Positivstellensatz proofs

This page was built for publication: Tight size-degree bounds for sums-of-squares proofs