[Colloquium] JOB TALK TODAY: Madhur Tulsiani, Princeton

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Friday, February 11, 2011
Time: 2:30 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------

Speaker:		Madhur Tulsiani

From:		Princeton University

Web page:	http://www.math.ias.edu/~madhurt/

Title: 		The Effectiveness and Limitations of Convex Relaxations

Abstract:  	Linear and semidefinite relaxations are among the most powerful tools
in the design of approximation algorithms. In this talk I will outline
some of my research aimed at understanding the effectiveness and
limitations of algorithms based on such relaxations.

I will describe how to formalize and reason about computational
models, which captures the notion of "increasingly powerful convex
relaxations". Such models, which are based on various hierarchies of
relaxations defined in the Operations Research community, capture some
of the best known algorithms. I will discuss lower bounds in these
models, which can be viewed as unconditional lower bounds for a
general and powerful class of algorithms.

I will also describe some cases when such convex relaxations can
achieve provably optimal approximation guarantees and mention some
problems for which understanding such questions remains open.

Host: 		Laci Babai

Refreshments will be served following the talk at 3:30 in Ryerson 255.