时间：2014年6月20日（周五）下午2:00-3:00
地点：曹光彪主楼201室
题目：Deterministic sorting in O(nloglogn) time and linear space
摘要：We will present a deterministic algorithm for integer sorting with time O(nloglogn) and linear space. This result was published on STOC and the journal version was published in 2004. It remains the current best result for sorting. This result is cited in Wikipedia under integer sorting. A prior and weaker version of this result published by me on integer sorting is cited in the MIT "Introduction to Algorithms" textbook, the second and the third editions (most recent edition).
报告者简介：Yijie Han is from Hanhzhou, Zhejiang, China. He obtained his bachelor's degree from University of Science and Technology of China, master's and Ph.D. from Duke University. He is currently with University of Missouri at Kansas City. His research is mainly in algorithms and parallel algorithms. Parallel algorithms designed by him for linked list coloring, selection, all pairs shortest paths (coauthored with Reif and Pan) , integer sorting (coauthored with Shen), maximal independent set, maximal matching, delta+1 vertex coloring, minimum spanning tree (coauthored with Chong and Lam) are the currently best results for these topics. His sequential algorithms for all pairs shortest paths and integer sorting are cited in the MIT "Introduction to Algorithms" textbook.
