|
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 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. |