scientific article; zbMATH DE number 2086404

MaRDI QIDQ4736859zbMATH 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/2285/22850419.htm

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20)

Recommendations

• scientific article; zbMATH DE number 1916823
• Complexity of semialgebraic proofs with restricted degree of falsity
• Complexity of Semialgebraic Proofs with Restricted Degree of Falsity
• Semialgebraic complexity of functions
• On the width of semialgebraic proofs and algorithms
• scientific article; zbMATH DE number 2110622
• Proof complexity meets algebra
• Proof Complexity Meets Algebra
• Semialgebraic Proofs and Efficient Algorithm Design
• scientific article; zbMATH DE number 18648

Cited in

(31)

• Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
• Complexity of semialgebraic proofs with restricted degree of falsity
• Proof Complexity Meets Algebra
• Semialgebraic Proofs and Efficient Algorithm Design
• Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
• Perfect matching in random graphs is as hard as Tseitin
• Proof complexity and the binary encoding of combinatorial principles
• Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
• On the width of semialgebraic proofs and algorithms
• Proof complexity meets algebra
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• MaxSAT Resolution and Subcube Sums
• Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
• scientific article; zbMATH DE number 1916823 (Why is no real title available?)
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization
• scientific article; zbMATH DE number 2086627 (Why is no real title available?)
• Sum-of-squares bounds via Boolean function analysis
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• The relation between polynomial calculus, Sherali-Adams, and sum-of-squares proofs
• On the hardest problem formulations for the 0/1 Lasserre hierarchy
• scientific article; zbMATH DE number 7378399 (Why is no real title available?)
• Sum of Squares Bounds for the Empty Integral Hull Problem
• scientific article; zbMATH DE number 7250156 (Why is no real title available?)
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
• First-order reasoning and efficient semi-algebraic proofs
• Complexity of optimizing over the integers
• Complexity of Semialgebraic Proofs with Restricted Degree of Falsity
• Algebraic proof systems over formulas.
• Tight rank lower bounds for the Sherali-Adams proof system
• A framework for space complexity in algebraic proof systems
• Rank bounds for a hierarchy of Lovász and Schrijver

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 Q4736859)