Counting and Sampling of Lattice points in Polytopes.

This research project was initially concerned with the computational
problem of counting lattice points in polytopes. Our goal was to
develop an algorithm whose input was the description of a polytope
in many dimensions, which would output the number of lattice points
that polytope contains. We were also interested in the related
problem of sampling a "Random" lattice point from the entire set
of lattice points.
Counting lattice points is an example of a "sharp P"-complete problem,
and these are notoriously difficult for computers to solve efficiently. If we
have as much time as we like, then there is no difficulty, but even at the
stage of 5 or 6 dimensions, the time taken by an exact algorithm can spiral
out of control. The goal of this project was to come up with algorithms to
approximately count lattice points (and in some cases, just to count
"boundary" lattice points, or vertices) in "polynomial-time". We had very
limited successes in this goal, as follows:
(a) We were able to show that a very simple Markov chain called the
"face-reversal chain" is rapidly mixing on Eulerian Orientations of
the triangular lattice, leading to an efficient sampling algorithm.
Eulerian Orientations correspond to the vertices of an appropriately
defined polytope; however this is a very special case of the general
vertex-sampling problem.
(b) We obtained results on counting lattice points of cell-bounded
contingency tables (when the number of rows is constant), and on
lattice points of all "sufficiently fat" polytopes.
However, the general case of "sampling lattice points", and even
"sampling contingency tables", still remains open.
During the early period of the research project, we extended the focus
of the project to consider the problem of sampling and counting Euler
tours of a given graph. We had some limited success with this notorious
open problem.
(c) We have been able to develop an algorithm to exactly
count and sample Euler tours of series-parallel graphs (a
very simple class).
(d) We also have a large amount of preliminary work on sampling
and approximately counting Euler tours of random regular graphs,
and we hope that we may be able to extend this to a polynomial-time
algorithm for the random model.
The program-of research intended for this project is not
completed (though the grant has ended), and the PI is continuing
work on the problem of sampling/approximately counting lattice
points, and the Euler tours problem.