The Complexity of Partial Orders - Theory/Algorithms talk by Ian Munro, U. Waterloo
Date
–
Title: The Complexity of Partial Orders
Speaker: Dr. J. Ian Munro
Cheriton School of Computer Science
University of Waterloo
Host: David Kirkpatrick
Abstract:
Comparison based problems, such as sorting or finding the maximum are
fundamental in computing. We will address several issues, old and new,
in the computational complexity of comparison based problems, focusing
on the long term development of techniques. Most notably, we will look
at the comparison minimization problems of placing a set of n values
into an arbitrary given partial order, and of completing the sort from
this stage. The parallel development of the algorithmics and of the
necessarily mathematical tools (such as graph entropy) will be
discussed in this context.