The University of Michigan Combinatorics Seminar


Abstract 

It is generally hard to count, or even estimate, how many integer points lie in a polytope P. Barvinok and Hartigan approach the problem by way of information theory, showing how to efficiently compute a random vector which samples the integer points of P with (computable) constant mass, but which may also land outside P. Thus, to count the integer points of P, it suffices to determine the frequency with which the random vector falls in P. I will present several upper bounds on this frequency. This problem may be expressed as a variant of the LittlewoodOfford problem, that is, of bounding the concentration of a sum of independent random variables. I will sketch connections between my work and earlier approaches to this problem. 