Theory Seminar - June 24

Event date: Friday, June 24, 2011, at 11:10 AM

Location: GB 244

SPEAKER: Pascal Koiran
Ecole Normale Superieure de Lyon
University of Toronto

TITLE: Random graphs without large dense subgraphs: are they hard to certify?

ABSTRACT:
Given a graph on n vertices, is there a subgraph induced by k vertices with edge density at least 0.5+epsilon ?
For suitable values of the parameters k and epsilon, the answer is NO for most graphs. It then makes sense to ask for an algorithm certifying that most graphs do not contain any dense k-subgraph. We propose efficient algorithms for certain values of the parameters, and identify other values for which this problem seems hard. This work is motivated by applications to compressed sensing, and more precisely to the computational complexity of the restricted isometry
property (no background in this area will be assumed).

This is joint work with Anastasios Zouzias.

Computer Science

University of Toronto

Theory Seminar - June 24

Computer Science