Title: A variant of backwards analysis applicable to order-dependent sets

Speaker: Martin Suderland, NYU

Date and time: 6pm (New York time), Tuesday, March 26, 2024

Place: WWH1314 (room 1314 Warren Weaver Hall, 251 Mercer Street)

...and on Zoom, details on the seminar mailing list

Backwards analysis is a simple, yet powerful technique used in analyzing the expected performance of randomized algorithms: a randomized incremental algorithm is seen as if it were running backwards in time, from output to input [Seidel 1993]. To be applicable, a key requirement is that the algorithm's output is independent of the randomization order. This needs to hold even for intermediate structures, assuming the same set of elements has been processed. We promote a variant, which can be applied to algorithms with order-dependent output. This variant of backwards analysis was introduced by [Junginger and Papadopoulou, DCG 2023]. As an example, we use the randomized incremental triangulation of a point set in $\mathbb{R}^d$, a generalization of Quicksort in higher dimensions, which has been cited by Seidel as a negative example, where backwards analysis could not be applied. We prove that the expected running time of this algorithm is $O(n \log n)$. This is joint work with Evanthia Papadopoulou.