Karthik Chandrasekaran gave a talk at TTI today on the feasibility of integer programs. Given a polytope defined by the inequalities in dimension , can we say whether the polytope contains an integer point? In general, the problem is NP-hard, but efficient algorithms are known for special sub-cases. The goal in this talk was to understand if random instances of the problem are also hard.

The first thing to figure out is what do we mean by a random instance? Consider a point and the sphere of radius around . Now draw vectors uniformly from the surface of the unit sphere, and consider the polytope defined by faces which are tangent to at for . That is, the vector is the normal vector of that face. This defines a random polytope whose distribution depends on the parameters . The goal is to find how scales with and such that with high probability, the polytope contains an integer point for all .

If the radius is too small, then this will be hard to do because guaranteeing that an integer point is in the interior for all becomes hard. If , then we will always have an integer point. What should the real scaling for look like?

The simple form of the main result is that if and , with high probability the polytope will have an integer point for every . Conversely, if , then with high probability the polytope “centered” at with not contain an integer point. Note that if the number of faces is linear in , then a constant radius is sufficient. I’m trying to square that with the “infinite dimensional spheres have vanishing volume and expanding surface area” but I think the fact that the polytope is “pointy” means that geometry gives better intuition.

To prove these bounds on , they make a connection to the discrepancy of random Gaussian matrices (which approximate the random unit vector row matrices). The paper is on arxiv for those who want to take a look.