演讲人：
张勤 丹麦奥胡斯大学
时间： 2012-01-03 15:00-2012-01-03 16:00
地点：FIT 1-222
内容：
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.
个人简介:
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.
