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

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

Recommendations

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

Cited in

(12)

• Computing parametric rational generating functions with a primal Barvinok algorithm
• On the number of integer points in translated and expanded polyhedra
• Neighborhood complexes and generating functions for affine semigroups
• Motivic Poincaré series, toric singularities and logarithmic Jacobian ideals
• Complexity of short generating functions
• Algorithms for lattice games
• Short rational generating functions for lattice point problems
• A plethora of polynomials: a toolbox for counting problems
• Short Presburger Arithmetic Is Hard
• Presburger arithmetic with algebraic scalar multiplications
• Generating function for the figurative numbers of regular polyhedron
• Analytic expansions and Poincaré series

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)