ON SAMPLING INTEGER POINTS IN POLYHEDRA
Igor Pak · Foundations of Computational Mathematics · 2002
. We investigate the problem of sampling integer points in rational polyhedra provided an oracle for counting these integer points. When dimension is bounded, this assumption is justified in view of a recent algorithm due to Barvinok [B1,B2,BP]. We show that the exactly uniform sampling is possible in full generality, when the oracle is called polynomial number of times. Further, when Barvinok's algorithm is used, poly-log number of calls suffices.