Georgia Institute of Technology College of Sciences

I will show a new approach based on the discrepancy of the constraint matrix to verify integer feasibility of polytopes. I will then use this method to show a threshold phenomenon for integer feasibility of random polytopes. The random polytope model that we consider is P(n,m,x0,R) - these are polytopes in n-dimensional space specified by m "random" tangential hyperplanes to a ball of radius R centered around the point x0. We show that there exist constants c_1 < c_2 such that with high probability, the random polytope P(n,m,x0=(0.5,...,0.5),R) is integer infeasible if R is less than c_1sqrt(log(2m/n)) and the random polytope P(n,m,x0,R) is integer feasible for every center x0 if the radius R is at least c_2sqrt(log(2m/n)). Thus, a transition from infeasibility to feasibility happens within a constant factor increase in the radius. Moreover, if the polytope contains a ball of radius Omega(log (2m/n)), then we can find an integer solution with high probability (over the input) in randomized polynomial time. This is joint work with Santosh Vempala.