[Colloquium] TTIC Talks: Karthekeyan Chandrasekaran, Georgia Tech

[Liv Leader]

When:     Tomorrow, Tuesday June 26th @ 11 a.m.

Where:     TTIC, 6045 S. Kenwood Avenue, Room #526

Who:       Karthekeyan Chandrasekaran, Georgia Tech

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, and a bound on the discrepancy of
random Gaussian matrices. We also give an efficient algorithm to find
an integer point in random polytopes with large inscribed ball by
extending Lovett-Meka's algorithm for finding low discrepancy
solutions.


Host: Madhur Tulsiani, madhurt at ttic.edu
-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu
Web-   www.ttic.edu