Sorting under partial information (without the ellipsoid algorithm).

Jean Cardinal, Samuel Fiorini, Gwenal Joret, Raphal M. Jungers, J. Ian Munro

Browse the full STOC paper archive.