Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
From MaRDI portal
Publication:650840
DOI10.1016/J.JSC.2011.08.007zbMath1247.13026OpenAlexW2161293461MaRDI QIDQ650840
Jesús A. De Loera, Jon Lee, Peter N. Malkin, Susan Margulies
Publication date: 7 December 2011
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jsc.2011.08.007
Symbolic computation and algebraic computation (68W30) Coloring of graphs and hypergraphs (05C15) Solving polynomial systems; resultants (13P15)
Related Items (8)
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares ⋮ DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization ⋮ Weak orientability of matroids and polynomial equations ⋮ Solving hybrid Boolean constraints in continuous space via multilinear Fourier expansions ⋮ On the complexity of Hilbert refutations for partition ⋮ A Polyhedral Characterization of Border Bases ⋮ Complexity, exactness, and rationality in polynomial optimization ⋮ Complexity, exactness, and rationality in polynomial optimization
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exponential lower bounds for the tree-like Hajós calculus
- Computing border bases
- Semidefinite representations for finite varieties
- Bounds for the degrees in the Nullstellensatz
- On 4-critical planar graphs with high edge density
- Good degree bounds on Nullstellensatz refutations of the induction principle
- Stable sets and polynomials
- Semidefinite programming relaxations for semialgebraic problems
- On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
- Recognizing graph theoretic properties with polynomial ideals
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Constructive generation of very hard 3-colorability instances
- Algebraic characterization of uniquely vertex colorable graphs
- A branch-and-cut algorithm for graph coloring
- Polynomials nonnegative on a grid and discrete optimization
- Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization
- Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
- Algèbre linéaire sur $K[X_1,\dots,X_n$ et élimination]
- New methods to color the vertices of a graph
- Combinatorial Nullstellensatz
- Sharp Effective Nullstellensatz
- Polynomials that Vanish on Distinct $n$ th Roots of Unity
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Using Hajós’ Construction to Generate Hard Graph 3-Colorability Instances
- CoCoALib: A C++ Library for Computations in Commutative Algebra... and Beyond
- Frozen development in graph coloring
This page was built for publication: Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
