Verifying partial orders

We present a randomized algorithm which uses O(n(log n)1/3) expected comparisons to verify that a given partial order holds on n elements from an unknown total order.