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

zbMATH Open1099.05003MaRDI QIDQ5491012FDOQ5491012

Authors: Alexander Barvinok 

Publication date: 26 September 2006

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

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)

Cited In (11)

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

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)