日時：4月22日（月）15:00 - 16:30

Generalized Sorting

Sampath Kannan (University of Pennsylvania)

The well-known problem of sorting still has some interesting
variations that have not been fully explored. In this talk we
consider the problem when we are given a graph that specifies which
pairs of elements we are allowed to compare.
Under the promise that making all the comparisons will reveal a total
order, we show that it is possible to design a randomized algorithm
that makes about n^{3/2} comparisons on any graph and determines the
total order. 

This is joint work with Zhiyi Huang and Sanjeev Khanna.

問合せ先：瀧本（C03）