scientific article; zbMATH DE number 2086627

MaRDI QIDQ4737162zbMATH OpenFDO

Authors Edward A. Hirsch, Dima Grigoriev, Dmitrii V. Pasechnik

Publication date 11 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2380/23800257.htm

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1916823
• Complexity of Semialgebraic Proofs with Restricted Degree of Falsity
• scientific article; zbMATH DE number 2086404
• scientific article; zbMATH DE number 5161489
• Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies

Cited in

(9)

• Tight size-degree bounds for sums-of-squares proofs
• Nullstellensatz size-degree trade-offs from reversible pebbling
• The relation between polynomial calculus, Sherali-Adams, and sum-of-squares proofs
• scientific article; zbMATH DE number 5161489 (Why is no real title available?)
• Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies
• On the width of semialgebraic proofs and algorithms
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?
• First-order reasoning and efficient semi-algebraic proofs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4737162)