[Colloquium] 3/8 Research at TTIC: Yury Makarychev, TTIC

[Alicia McClarin]

*When:*      Friday, March 8th. Refreshments at noon. Talk begins at 12:20.

*Where:*    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

*Who: *      Yury Makarychev, TTIC

*Title: *      Performance of Johnson-Lindenstrauss Transform for k-Means
and
               k-Medians Clustering

*Abstract:*  Consider an instance of Euclidean k-means or k-medians
clustering. We show that the cost of the optimal solution is preserved
up to a factor of (1+ε) under a projection onto a random
O(log(k/ε)/ε^2)-dimensional subspace. Further, the cost of every
clustering is preserved within (1+ε). More generally, our result
applies to any dimension reduction map satisfying a mild
sub-Gaussian-tail condition. Our bound on the dimension is nearly
optimal. Additionally, our result applies to Euclidean k-clustering
with the distances raised to the p-th power for any constant p.

For k-means, our result resolves an open problem posed by Cohen,
Elder, Musco, Musco, and Persu (STOC 2015); for k-medians, it answers
a question raised by Kannan.

Based on a joint work with Konstantin Makarychev and Ilya Razenshteyn.

********************************************************************************************************

*Research at TTIC Seminar Series*

TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact Nathan Srebro at nati at ttic.edu
<mcallester at ttic.edu>

-- 
*Alicia McClarin*
*Toyota Technological Institute at Chicago*
*6045 S. Kenwood Ave., **Office 510*
*Chicago, IL 60637*
*773-702-5370*
*www.ttic.edu* <http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190301/9c88eeae/attachment-0001.html>