Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
From MaRDI portal
Publication:5091776
Recommendations
Cites work
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- Anneaux preordonnes
- Approximability and proof complexity
- Complexity of Null- and Positivstellensatz proofs
- Complexity of Positivstellensatz proofs for the knapsack
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Convex relaxations and integrality gaps
- Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures
- Global optimization with polynomials and the problem of moments
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- scientific article; zbMATH DE number 2086404 (Why is no real title available?)
- Hypercontractivity, sum-of-squares proofs, and their applications
- Ideals, Varieties, and Algorithms
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Linear vs. semidefinite extended formulations
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Lower bounds on the size of semidefinite programming relaxations
- Narrow proofs may be maximally long
- Optimality of size-degree tradeoffs for polynomial calculus
- Optimality of size-width tradeoffs for resolution
- Short proofs are narrow—resolution made simple
- Space Complexity in Propositional Calculus
- Strong duality in lasserre's hierarchy for polynomial optimization
- Tight size-degree bounds for sums-of-squares proofs
- Vector spaces with an order unit
Cited in
(14)- Nullstellensatz size-degree trade-offs from reversible pebbling
- High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts
- SOS lower bounds with hard constraints: think global, act local
- Sum of squares bounds for the ordering principle
- scientific article; zbMATH DE number 7087310 (Why is no real title available?)
- High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
- MaxSAT Resolution and Subcube Sums
- Circular (Yet Sound) Proofs in Propositional Logic
- On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
- Perfect matching in random graphs is as hard as Tseitin
- Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
- MaxSAT resolution with inclusion redundancy
- Bounds on the total coefficient size of nullstellensatz proofs of the pigeonhole principle
- Refuting perfect matchings in spectral expanders is hard
This page was built for publication: Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091776)
