|
Graph Entropy, Posets, and Sorting Under Partial InformationGraph Entropy, Posets, and their applications in SUPI (pdf)Preetum Nakkiran and Matthew Francis-Landau. 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 lower-bound the
query complexity of algorithms for SUPI, and exhibit algorithms which perform
provably close to the
lower-bound.
In some sense this is an information-theoretic 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 entropy-like functional on graphs): Our initial comparisons have the structure of a poset, and the lower-bound is related to the graph-entropy of this poset. In this survey, we review various fundamental properties of posets and graph-entropy, and eventually see their application in proving lower-bounds and optimality of algorithms for SUPI. We try to present all the required ideas from scratch, adding intuition and examples along the way. |