Showing 2024 · math.PRShow all
3 papers · 2 filters
math.PR2024
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…
math.PR2024
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…
math.PR2024
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…