Speaker:

Karthekeyan Chandrasekaran

Title:

Phase Transition in Random Integer Programs

Abstract:

We consider integer programs on random polytopes in R^n with m facets whose normal vectors are chosen independently from any spherically symmetric distribution. We show a phase transition phenomenon: a transition from integer infeasibility to integer feasibility happens within a constant factor increase in the radius of the largest inscribed ball. Our main tools are: a new connection between integer programming and matrix discrepancy, a bound on the discrepancy of random Gaussian matrices and Lovett-Meka's algorithm for finding low discrepancy solutions.