Speaker: Qin Zhang Aarhus University, Denmark
Time: 2012-01-03 15:00-2012-01-03 16:00
Venue: FIT 1-222
Abstract:
In this talk we will discuss an efficient sketch for Earth-Mover Distance. Our sketch achieves the same space complexity and approximation ratio as Andoni et. al (FOCS 2009). but (1) Our sketch is a linear mapping (embedding) to a product norm space. (2) Our sketch algorithm is much simpler. (3) Our effective use of the low-dimensionality property of a norm (we call Rademacher-dimension) may be of independent interest.
Short Bio:
Dr. Zhang is currently a Postdoc at Center for Massive Data Algorithmics, Computer Science Department, Aarhus University, working with Prof. Lars Arge. He obtained his Ph.D. degree in Computer Science and Engineering from Hong Kong University of Science and Technology in 2010, advised by Prof. Mordecai Golin and Dr. Ke Yi; and his B.Sc. degree in Computer Science from Fudan University in 2006. His current research interests include algorithms for massive data; data streams; algorithms on distributed data; data structures; external memory algorithms; database algorithms; communication complexity.
