scientific article; zbMATH DE number 2086404
From MaRDI portal
Publication:4736859
zbMATH Open1054.03035MaRDI QIDQ4736859FDOQ4736859
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
Title of this publication is not available (Why is that?)
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)
- Proof Complexity Meets Algebra
- Complexity of semialgebraic proofs with restricted degree of falsity
- 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
- MaxSAT Resolution and Subcube Sums
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
- Title not available (Why is that?)
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Sum of Squares Bounds for the Empty Integral Hull Problem
- Title not available (Why is that?)
- 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.
- A framework for space complexity in algebraic proof systems
- Tight rank lower bounds for the Sherali-Adams proof system
- Rank bounds for a hierarchy of Lovász and Schrijver
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
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)