May 22, Spring Quarter 2009: Thoery Seminar

1:00pm in 253 ICS

Sorting and Selection in Posets

By Constantinos Daskalakis, Richard M. Karp , Elchanan Mossel, Samantha Riesenfeld, Elad Verbin

Presented by Lowell Trott, UCI

The authors have presented several results in sorting and selection in partially ordered sets. This includes an algorithm that sorts a width- w poset of size n with optimal query complexity O(n(w + logn)).