A Generalization of Self-Improving Algorithms

Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances x1,cdots,xn follow some unknown product distribution. That is, xi comes from a fixed unknown distribution mathsfDi, and the xi's are drawn independently. After spending O(n1+varepsilon) time in a learning phase, the subsequent expected running time is O((n+ H)/varepsilon), where H ∈ HS,HDT, and HS and HDT are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the xi's under the group product distribution. There is a hidden partition of [1,n] into groups; the xi's in the k-th group are fixed unknown functions of the same hidden variable uk; and the uk's are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map uk to xi's are well-behaved. After an O(poly(n))-time training phase, we achieve O(n + HS) and O(nα(n) + HDT) expected running times for sorting and DT, respectively, where α(·) is the inverse Ackermann function.