The complexity of generating functions for integer points in polyhedra and beyond

MaRDI QIDQ5491012zbMATH OpenFDO

Authors Alexander Barvinok

Publication date 26 September 2006

zbMATH Keywords

Lattice point, rational polytope, generating function, rational function, Laurent polynomial, integer semigroup, Hilbert basis, efficient counting, computational complexity

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Exact enumeration problems, generating functions (05A15) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Lattices and convex bodies (number-theoretic aspects) (11H06) Lattice points in specified regions (11P21)

Recommendations

• Short rational generating functions for lattice point problems
• scientific article; zbMATH DE number 5222518
• Publication:4938470
• Integer points in polyhedra
• Computing parametric rational generating functions with a primal Barvinok algorithm

Cited in

(11)

• Complexity of short generating functions
• On the number of integer points in translated and expanded polyhedra
• Algorithms for lattice games
• Short Presburger Arithmetic Is Hard
• Neighborhood complexes and generating functions for affine semigroups
• Computing parametric rational generating functions with a primal Barvinok algorithm
• A plethora of polynomials: a toolbox for counting problems
• Generating function for the figurative numbers of regular polyhedron
• Short rational generating functions for lattice point problems
• scientific article; zbMATH DE number 7407776 (Why is no real title available?)
• Motivic Poincaré series, toric singularities and logarithmic Jacobian ideals

Describes a project that uses

Uses Software

• LattE

This page was built for publication: The complexity of generating functions for integer points in polyhedra and beyond

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5491012)