The entropy of backwards analysis

TY - GEN

T1 - The entropy of backwards analysis

AU - Knudsen, Mathias Bæk Tejs

AU - Thorup, Mikkel

N1 - Conference code: 29

PY - 2018

Y1 - 2018

N2 - Backwards analysis, first popularized by Seidel, is often the simplest most elegant way of analyzing a randomized algorithm. It applies to incremental algorithms where elements are added incrementally, following some random permutation, e.g., incremental Delauney triangulation of a pointset, where points are added one by one, and where we always maintain the Delauney triangulation of the points added thus far. For backwards analysis, we think of the permutation as generated backwards, implying that the ith point in the permutation is picked uniformly at random from the i points not picked yet in the backwards direction. Backwards analysis has also been applied elegantly by Chan to the randomized linear time minimum spanning tree algorithm of Karger, Klein, and Tarjan. The question considered in this paper is how much randomness we need in order to trust the expected bounds obtained using backwards analysis, exactly and approximately. For the exact case, it turns out that a random permutation works if and only if it is minwise, that is, for any given subset, each element has the same chance of being first. Minwise permutations are known to have ⊖(n) entropy, and this is then also what we need for exact backwards analysis. However, when it comes to approximation, the two concepts diverge dramatically. To get backwards analysis to hold within a factor, the random permutation needs entropy O(n=). This contrasts with minwise permutations, where it is known that a 1+" approximation only needs ⊖(log(n=")) entropy. Our negative result for backwards analysis essentially shows that it is as abstract as any analysis based on full randomness.

AB - Backwards analysis, first popularized by Seidel, is often the simplest most elegant way of analyzing a randomized algorithm. It applies to incremental algorithms where elements are added incrementally, following some random permutation, e.g., incremental Delauney triangulation of a pointset, where points are added one by one, and where we always maintain the Delauney triangulation of the points added thus far. For backwards analysis, we think of the permutation as generated backwards, implying that the ith point in the permutation is picked uniformly at random from the i points not picked yet in the backwards direction. Backwards analysis has also been applied elegantly by Chan to the randomized linear time minimum spanning tree algorithm of Karger, Klein, and Tarjan. The question considered in this paper is how much randomness we need in order to trust the expected bounds obtained using backwards analysis, exactly and approximately. For the exact case, it turns out that a random permutation works if and only if it is minwise, that is, for any given subset, each element has the same chance of being first. Minwise permutations are known to have ⊖(n) entropy, and this is then also what we need for exact backwards analysis. However, when it comes to approximation, the two concepts diverge dramatically. To get backwards analysis to hold within a factor, the random permutation needs entropy O(n=). This contrasts with minwise permutations, where it is known that a 1+" approximation only needs ⊖(log(n=")) entropy. Our negative result for backwards analysis essentially shows that it is as abstract as any analysis based on full randomness.

U2 - 10.1137/1.9781611975031.56

DO - 10.1137/1.9781611975031.56

M3 - Article in proceedings

SP - 867

EP - 880

BT - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Czumaj, Artur

PB - Society for Industrial and Applied Mathematics

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 7 January 2018 through 10 January 2018

ER -