6 papers
Distances in -ary recursive trees
Kiran Bhutani, Ravi Kalpathy, Florian Lesny +2
We introduce the -ary recursive tree, a tree structure that starts with a single node. At each step of the growth process, a random node, called the recruiter, is selected, and…
Probabilistic analysis of optimal multi-pivot QuickSort
Cecilia Holmgren, Jasper Ischebeck, Daniel Krenn +2
We consider a multi-pivot QuickSort algorithm using pivot elements to partition a nonsorted list into sublists in order to proceed recursively on these subli…
Random -SAT: The set of atoms of the limiting empirical marginal distribution
Noela Müller, Ralph Neininger, Haodong Zhu
We show that the set of atoms of the limiting empirical marginal distribution in the random -SAT model is , for all clause-to-variable densities up to the…
On Policy Evaluation Algorithms in Distributional Reinforcement Learning
Julian Gerstenberg, Ralph Neininger, Denis Spiegel
We introduce a novel class of algorithms to efficiently approximate the unknown return distributions in policy evaluation problems from distributional reinforcement learning (DRL).…
On fine fluctuations of the complexity of the QuickSelect algorithm
Jasper Ischebeck, Ralph Neininger
The Quickselect algorithm (also called FIND) is a fundamental algorithm for selecting ranks or quantiles within a set of data. Grübel and Rösler showed that the number of key compa…
Patricia's Bad Distributions
Louigi Addario-Berry, Pat Morin, Ralph Neininger
The height of a random PATRICIA tree built from independent, identically distributed infinite binary strings with arbitrary diffuse probability distribution on $\{0,1\}^\mathbb…