Tight size-degree bounds for sums-of-squares proofs
From MaRDI portal
Publication:1686838
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
semidefinite programmingsizedegreeranklower boundcliqueresolutionPositivstellensatzproof complexitysums-of-squaresLasserre
Related Items
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
