### DIMACS Theoretical Computer Science Seminar

Title: An Elementary Proof of the Restricted Invertibility Theorem

Speaker: **Nikhil Srivastava**, IAS

Date: Wednesday, February 9, 2011 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We give an elementary proof of a generalization of Bourgain and
Tzafriri's Restricted Invertibility Theorem, which says roughly that
any matrix with columns of unit length and bounded operator norm has a
large coordinate subspace on which it is well-invertible. Our proof
gives the tightest known form of this result, is constructive, and
provides a deterministic polynomial time algorithm for finding the
desired subspace.

Joint work with Dan Spielman.