[Colloq] Reminder: Talk today, Anupam Gupta - "Algorithmic Notions of Dimension"

[Rachel Kalweit]

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


_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq