[Colloq] Anupam Gupta - "Algorithmic Notions of Dimension"

Rachel Kalweit rachelb at ccs.neu.edu
Tue Apr 24 09:14:57 EDT 2007


College of Computer and Information Science Colloquium

Presents:
Anupam Gupta
Carnegie Mellon University

Who will speak on:
“Algorithmic Notions of Dimension”

Monday, April 30, 2007
11:00 am
366 West Village H
Northeastern University


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.

Speaker Bio:
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 
recipient of an Alfred P. Sloan Research Fellowship, and the NSF Career 
award.

Host: Rajmohan Rajaraman




More information about the Colloq mailing list