Exponential lower bound for static semi-algebraic proofs

DOI10.1007/3-540-45465-9_23MaRDI QIDQ4737162zbMATH OpenFDO

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

Publication date 11 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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
• Complexity of semi-algebraic proofs
• 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: Exponential lower bound for static semi-algebraic proofs

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