  We study integer programming instances over polytopes P(A,b)={x:Ax<=b} where
the constraint matrix A is random, i.e., its entries are i.i.d. Gaussian or,
more generally, its rows are i.i.d. from a spherically symmetric distribution.
The radius of the largest inscribed ball is closely related to the existence of
integer points in the polytope. We show that for m=2^O(sqrt{n}), there exist
constants c_0 < c_1 such that with high probability, random polytopes are
integer feasible if the radius of the largest ball contained in the polytope is
at least c_1sqrt{log(m/n)}; and integer infeasible if the largest ball
contained in the polytope is centered at (1/2,...,1/2) and has radius at most
c_0sqrt{log(m/n)}. Thus, random polytopes transition from having no integer
points to being integer feasible within a constant factor increase in the
radius of the largest inscribed ball. We show integer feasibility via a
randomized polynomial-time algorithm for finding an integer point in the
polytope.
  Our main tool is a simple new connection between integer feasibility and
linear discrepancy. We extend a recent algorithm for finding low-discrepancy
solutions (Lovett-Meka, FOCS '12) to give a constructive upper bound on the
linear discrepancy of random matrices. By our connection between discrepancy
and integer feasibility, this upper bound on linear discrepancy translates to
the radius lower bound that guarantees integer feasibility of random polytopes.
