Sorting Under Partial Information (joint work with J. Kahn)
We reconsider the old problem of sorting under partial information,
and give a polynomial time algorithm for the following task:

Given a partial order P, find a sequence of comparisons (questions of the form, "is x < y?")
which sorts P using O(log(e(P))) comparisons in the worst case, where e(P) is the number of linear extensions of P.

Jeong Han Kim
Korea Institute For Advanced Study (KIAS)
Department School of Computational Sciences
Education​
1993 Ph.D. in Mathematics, Rutgers University, USA
1987 MS in Mathematics, Yonsei University, Seoul, Korea
1985 BS in Physics, Yonsei University, Seoul, Korea
Positions held
2013-present Professor, School of Computational Sciences, Korea Institute For Advanced Study, Seoul, Korea
2006-2013 Professor, Yonsei University, Korea, Seoul, Korea
2008-2011 President, National Institute for Mathematical Sciences (NIMS)
1997-2007 Researcher, Senior Researcher, Microsoft Research, Redmond WA USA
1993-1997 Member of Technical Staff, Senior Technical Staff, Principal Technical Staff Information Sciences Research Center, AT&T (Bell) Labs-Research, Murray Hill NJ USA
Awards & Honours
Sam-il Cutral Awards (Natural sciences), 2020
Kyung-Am Award in Natural Sciences, 2008
Role Model Award for Scientists and Engineers, 2007
Underwood Chair Professor (Yonsei University) 2007
Invited Speaker, International Congresses of Mathematicians (ICM), 2006
Fulkerson Prize, August, 1997
Sloan Research Fellowship, February, 1997
Sloan Dissertation Fellowship, September, 1992
Yon-Am Fellowship, March, 1985 -February, 1