Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
From MaRDI portal
Publication:5091776
DOI10.4230/LIPIcs.CCC.2019.24OpenAlexW2965705192MaRDI QIDQ5091776
Tuomas Hakoniemi, Albert Atserias
Publication date: 27 July 2022
Full work available at URL: https://arxiv.org/abs/1811.01351
degreelower boundsproof complexitypositivstellensatztrade-offssums-of-squaresmonomial sizesemialgebraic proof systems
Related Items
Unnamed Item ⋮ Circular (Yet Sound) Proofs in Propositional Logic ⋮ On vanishing sums of roots of unity in polynomial calculus and sum-of-squares ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Sum of squares bounds for the ordering principle ⋮ MaxSAT Resolution and Subcube Sums
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimality of size-width tradeoffs for resolution
- Tight size-degree bounds for sums-of-squares proofs
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Anneaux preordonnes
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- Global Optimization with Polynomials and the Problem of Moments
- Convex Relaxations and Integrality Gaps
- Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász–Schrijver Procedures
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Optimality of size-degree tradeoffs for polynomial calculus
- Space Complexity in Propositional Calculus
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Short proofs are narrow—resolution made simple
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Ideals, Varieties, and Algorithms
- Narrow Proofs May Be Maximally Long
- Vector spaces with an order unit
- Linear vs. semidefinite extended formulations
- Hypercontractivity, sum-of-squares proofs, and their applications
- Approximability and proof complexity
- 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
- Strong duality in lasserre's hierarchy for polynomial optimization
