
Graph Entropy, Posets, and Sorting Under Partial InformationGraph Entropy, Posets, and their applications in SUPI (pdf)Preetum Nakkiran and Matthew FrancisLandau. 2015.
Abstract: In traditional comparison sorting, we are given a set of n elements with no a
priori information about
their order. Uniquely identifying a permutation requires log n! ∼ n log n bits,
and therefore Ω(n log n)
comparisons. In the setting of sorting under partial information (SUPI), we are
given some initial
comparisons, and would like to minimize the number of additional “comparison
oracle” calls required to
sort, given our partial information. Similar to the traditional setting, we
would like to lowerbound the
query complexity of algorithms for SUPI, and exhibit algorithms which perform
provably close to the
lowerbound.
In some sense this is an informationtheoretic question: we are given some partial information about the ordering, and want to know how much additional information is required to determine the ordering. The bulk of our survey involves making this precise, which requires the concepts of posets (partially ordered sets) and “graph entropy” (an entropylike functional on graphs): Our initial comparisons have the structure of a poset, and the lowerbound is related to the graphentropy of this poset. In this survey, we review various fundamental properties of posets and graphentropy, and eventually see their application in proving lowerbounds and optimality of algorithms for SUPI. We try to present all the required ideas from scratch, adding intuition and examples along the way. 