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