[Colloquium] TTIC Colloquium: Moses Charikar, Princeton University

[Liv Leader]

REMINDER:

When:     Friday, November 18 @ 11 a.m.

Where:   TTIC Conference Room #526, 6045 S. Kenwood Avenue, 5th Floor

Who:      Moses Charikar, Princeton University

Title:       Dimension Reduction in L_1

Given a set of n points in a normed space, how many dimensions are
needed to represent all distances within a specific distortion ? This
dimension-distortion tradeoff is well understood for the L_2 norm,
where O(log n) dimensions suffice to preserve distances almost
exactly. In sharp contrast, the situation for L_1 is far from
understood and there is a significant gap between upper and lower
bounds. In this talk, I will survey what we currently know about
dimension reduction in L_1 and present the first near linear lower
bounds for this question.

Host: Yury Makarychev, yury at ttic.edu



-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20111117/d32f6e04/attachment.htm