The Hilbert zonotope and a polynomial time algorithm for universal Gröbner bases.

DOI10.1016/S0196-8858(02)00509-2zbMath1039.13018arXivmath/0207135MaRDI QIDQ1408266

Shmuel Onn, Eric K. Babson, Rekha R. Thomas

Publication date: 15 September 2003

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0207135

zbMATH Keywords

Gröbner basispolynomial ideal theorycomplexity of algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Software, source code, etc. for problems pertaining to commutative algebra (13-04) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Related Items

Minimal average degree aberration and the state polytope for experimental designs ⋮ The complexity of vector partition ⋮ Vanishing configurations in network dynamics with asynchronous updates ⋮ Alexander duality in experimental designs ⋮ Betti numbers of polynomial hierarchical models for experimental designs ⋮ Gröbner Bases of Convex Neural Code Ideals (Research) ⋮ The Number of Gröbner Bases in Finite Fields (Research) ⋮ Small Gröbner fans of ideals of points ⋮ Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz ⋮ Geometric characterization of data sets with unique reduced Gröbner bases ⋮ The Algebraic Method in Quadrature for Uncertainty Quantification ⋮ Nowhere-zero flow polynomials ⋮ Toric varieties and Gröbner bases: the complete \(\mathbb{Q}\)-factorial case ⋮ Permutohedra and minimal matrices

Cites Work

• The Gröbner fan of an ideal
• Standard bases and geometric invariant theory. I: Initial ideals and state polytopes
• The number of generators of a colength N ideal in a power series ring
• Separable partitions
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• On the number of corner cuts
• Gröbner bases of lattices, corner polyhedra, and integer programming
• The Vector Partition Problem for Convex Objective Functions
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• A Polynomial Time Algorithm for Shaped Partition Problems
• A Lower Bound for the Volume of Strictly Convex Bodies with many Boundary Lattice Points
• Cutting corners