Skip to main content
6 of 7
added 1 character in body
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Approximate volume computation and lattice point enumeration - hardness

Both volume computation and lattice point enumeration of convex polyhedron are $\#P$ hard. However there is a randomized polytime algorithm for constant factor approximation for volume computation.

  1. Is there a randomized polytime algorithm for constant factor approximation for lattice point enumeration as well?

  2. Is it $\oplus P$ complete to decide if a convex body has odd number of integer points?

If the polytope is convex and also centrally symmetric then what is the situation for 1., 2. and approximate volume computation?

Turbo
  • 13.9k
  • 1
  • 27
  • 76