[Colloquium] [TTIC Talks] TTIC Talks: Karthekeyan Chandrasekaran, Georgia Tech

[Madhur Tulsiani]

Just a reminder: Karthik's talk starts at 11.

Madhur

On Mon, Jun 25, 2012 at 4:18 PM, Liv Leader <lleader at ttic.edu> wrote:
> 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