Events - Colloquia & Seminars

CCIS Colloquium Spring 2007

Algorithmic Notions of Dimension

Speaker: Anupam Gupta

Affiliation: CMU

Date: Monday, April 30, 2007

Talk: 11:00 a.m., 366 WVH

Abstract

A common feature of many algorithmic problems today is the presence of huge quantities of data, much of it residing in very high-dimensional space. This is often a problem, since high-dimensional data is "complex", and indeed, the performance of many existing algorithms has an exponential dependence on the dimension. Hence, a lot of effort is being spent on trying to get around this so-called "curse of dimensionality".

In this talk, I will discuss some research attempting to understand the complexity of metric spaces, and their algorithmic applications. In particular, I will talk about some lines of work trying to define the "intrisic" dimension of a metric space (as opposed to the dimension of the given representation), with the goal of developing tools and algorithms that have a dependence on only the intrinsic dimension of the data set.

Brief Biography

Anupam Gupta received the B.Tech degree in Computer Science from Indian Institute of Technology, Kanpur in 1996, and the PhD degree in Computer Science from the University of California, Berkeley, in 2000. After spending two years at Lucent Bell Labs in Murray Hill, New Jersey, he joined Carnegie Mellon University in January 2003, where he is currently an Assistant Professor in the Computer Science Department. His research interests are in the area of theoretical Computer Science, primarily in developing approximation algorithms for NP-hard optimization problems, and understanding the algorithmic properties of metric spaces. He is the recepient of an Alfred P. Sloan Research Fellowship, and the NSF Career award.