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