Publications (65)
Thermal WIMPs and the Scale of New Physics: Global Fits of Dirac Dark Matter Effective Field Theories
The GAMBIT Collaboration, Peter Athron, Neal Avis Kozar +24
We assess the status of a wide class of WIMP dark matter (DM) models in light of the latest experimental results using the global fitting framework . We perform a…
Deterministic Cache-Oblivious Funnelselect
Gerth Stølting Brodal, Sebastian Wild
In the multiple-selection problem one is given an unsorted array of elements and an array of query ranks , and the task is to return, in sorted order, t…
Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts
Raphael Reitzig, Sebastian Wild
Given a set of n sticks of various (not necessarily different) lengths, what is the largest length so that we can cut k equally long pieces of this length from the given set of sti…
A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment
Raphael Reitzig, Sebastian Wild
Proportional apportionment is the problem of assigning seats to parties according to their relative share of votes. Divisor methods are the de-facto standard solution, used in many…
An Optimal Randomized Algorithm for Finding the Saddlepoint
Justin Dallant, Frederik Haagensen, Riko Jacob +2
A \emph{saddlepoint} of an matrix is an entry that is the maximum of its row and the minimum of its column. Saddlepoints give the \emph{value} of a two-player zero-sum…
Top-Down Mergesort with Sorted Check Has Mergecost
Sebastian Wild
We consider standard top-down recursive Mergesort, where we do a single comparison before calling merge to check if the two recursively sorted subproblems happens to already be cor…
Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space
J. Ian Munro, Sebastian Wild
The range-minimum query (RMQ) problem is a fundamental data structuring task with numerous applications. Despite the fact that succinct solutions with worst-case optimal …
Global analyses of Higgs portal singlet dark matter models using GAMBIT
The GAMBIT Collaboration, Peter Athron, Csaba Balázs +15
We present global analyses of effective Higgs portal dark matter models in the frequentist and Bayesian statistical frameworks. Complementing earlier studies of the scalar Higgs po…
BBN constraints on MeV-scale dark sectors. Part II. Electromagnetic decays
Marco Hufnagel, Kai Schmidt-Hoberg, Sebastian Wild
Meta-stable dark sector particles decaying into electrons or photons may non-trivially change the Hubble rate, lead to entropy injection into the thermal bath of Standard Model par…
Average Case Analysis of Java 7's Dual Pivot Quicksort
Sebastian Wild, Markus E. Nebel
Recently, a new Quicksort variant due to Yaroslavskiy was chosen as standard sorting method for Oracle's Java 7 runtime library. The decision for the change was based on empirical…
Polyamorous Scheduling
Leszek GÄ sieniec, Benjamin Smith, Sebastian Wild
Finding schedules for pairwise meetings between the members of a complex social group without creating interpersonal conflict is challenging, especially when different relationship…
Simple approximation algorithms for Polyamorous Scheduling
Yuriy Biktairov, Leszek GÄ sieniec, Wanchote Po Jiamjitrak +3
In Polyamorous Scheduling, we are given an edge-weighted graph and must find a periodic schedule of matchings in this graph which minimizes the maximal weighted waiting time betwee…
Analysis of Branch Misses in Quicksort
Conrado MartÃnez, Markus E. Nebel, Sebastian Wild
The analysis of algorithms mostly relies on counting classic elementary operations like additions, multiplications, comparisons, swaps etc. This approach is often sufficient to qua…
Dark matter self-interactions from a general spin-0 mediator
Felix Kahlhoefer, Kai Schmidt-Hoberg, Sebastian Wild
Dark matter particles interacting via the exchange of very light spin-0 mediators can have large self-interaction rates and obtain their relic abundance from thermal freeze-out. At…
Partition-based Simple Heaps
Gerth Stølting Brodal, John Iacono, Casper Moldrup Rysgaard +1
We introduce a new family of priority-queue data structures: partition-based simple heaps. The structures consist of doubly-linked lists; order is enforced among data i…
Median-of-k Jumplists and Dangling-Min BSTs
Markus E. Nebel, Elisabeth Neumann, Sebastian Wild
We extend randomized jumplists introduced by Brönnimann et al. (STACS 2003) to choose jump-pointer targets as median of a small sample for better search costs, and present randomi…
Analysis of Quickselect under Yaroslavskiy's Dual-Pivoting Algorithm
Sebastian Wild, Markus E. Nebel, Hosam Mahmoud
There is excitement within the algorithms community about a new partitioning method introduced by Yaroslavskiy. This algorithm renders Quicksort slightly faster than the case when…
A novel approach to derive halo-independent limits on dark matter properties
Francesc Ferrer, Alejandro Ibarra, Sebastian Wild
We propose a method that allows to place an upper limit on the dark matter elastic scattering cross section with nucleons which is independent of the velocity distribution. Our app…
Succinct Preferential Attachment Graphs
Ziad Ismaili Alaoui, Namrata, Sebastian Wild
Computing over compressed data combines the space saving of data compression with efficient support for queries directly on the compressed representation. Such data structures are…
DAMA confronts null searches in the effective theory of dark matter-nucleon interactions
Riccardo Catena, Alejandro Ibarra, Sebastian Wild
We examine the dark matter interpretation of the modulation signal reported by the DAMA experiment from the perspective of effective field theories displaying Galilean invariance.…
Prospects of antideuteron detection from dark matter annihilations or decays at AMS-02 and GAPS
Alejandro Ibarra, Sebastian Wild
The search for cosmic antideuterons has been proposed as a promising method to indirectly detect dark matter, due to the very small background flux from spallations expected at the…
Signatures from Scalar Dark Matter with a Vector-like Quark Mediator
Federica Giacchino, Alejandro Ibarra, Laura Lopez Honorez +2
We present a comprehensive study of a model where the dark matter is composed of a singlet real scalar that couples to the Standard Model predominantly via a Yukawa interaction wit…
Hypersuccinct Trees -- New universal tree source codes for optimal compressed tree data structures and range minima
J. Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner +1
We present a new universal source code for distributions of unlabeled binary and ordinal trees that achieves optimal compression to within lower order terms for all tree sources co…
Sharp Gamma-ray Spectral Features from Scalar Dark Matter Annihilations
Alejandro Ibarra, Takashi Toma, Maximilian Totzauer +1
The search for sharp features in the gamma-ray spectrum is a promising approach to identify a signal from dark matter annihilations over the astrophysical backgrounds. In this pape…
Impact of vacuum stability, perturbativity and XENON1T on global fits of and scalar singlet dark matter
Peter Athron, Jonathan M. Cornell, Felix Kahlhoefer +3
Scalar singlet dark matter is one of the simplest and most predictive realisations of the WIMP (weakly-interacting massive particle) idea. Although the model is constrained from al…
Halo-independent comparison of direct detection experiments in the effective theory of dark matter-nucleon interactions
Riccardo Catena, Alejandro Ibarra, Andreas Rappelt +1
The theoretical interpretation of dark matter direct detection experiments is hindered by uncertainties of the microphysics governing the dark matter-nucleon interaction, and of th…
Randomized Communication and Implicit Graph Representations
Nathaniel Harms, Sebastian Wild, Viktor Zamaraev
We initiate the focused study of constant-cost randomized communication, with emphasis on its connection to graph representations. We observe that constant-cost randomized communic…
Determination of the Cosmic Antideuteron Flux in a Monte Carlo approach
Alejandro Ibarra, Sebastian Wild
We investigate in this paper the antideuteron flux produced in high energy collisions of cosmic rays with the interstellar matter. We employ the Monte Carlo generator DPMJET-III to…
Efficient Second-Order Shape-Constrained Function Fitting
David Durfee, Yu Gao, Anup B. Rao +1
We give an algorithm to compute a one-dimensional shape-constrained function that best fits given data in weighted- norm. We give a single algorithm that works for a va…
Dynamic Optimality Refuted -- For Tournament Heaps
J. Ian Munro, Richard Peng, Sebastian Wild +1
We prove a separation between offline and online algorithms for finger-based tournament heaps undergoing key modifications. These heaps are implemented by binary trees with keys st…
Model-independent comparison of annual modulation and total rate with direct detection experiments
Felix Kahlhoefer, Florian Reindl, Karoline Schäffner +2
The relative sensitivity of different direct detection experiments depends sensitively on the astrophysical distribution and particle physics nature of dark matter, prohibiting a m…
Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs
J. Ian Munro, Sebastian Wild
We present two stable mergesort variants, "peeksort" and "powersort", that exploit existing runs and find nearly-optimal merging orders with practically negligible overhead. Previo…
BBN constraints on the annihilation of MeV-scale dark matter
Paul Frederik Depta, Marco Hufnagel, Kai Schmidt-Hoberg +1
Thermal dark matter at the MeV scale faces stringent bounds from a variety of cosmological probes. Here we perform a detailed evaluation of BBN bounds on the annihilation cross sec…
Studying generalised dark matter interactions with extended halo-independent methods
Felix Kahlhoefer, Sebastian Wild
The interpretation of dark matter direct detection experiments is complicated by the fact that neither the astrophysical distribution of dark matter nor the properties of its parti…
Pivot Sampling in Dual-Pivot Quicksort
Markus E. Nebel, Sebastian Wild
The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries in its behavior. They were shown to…
Multiway Powersort
William Cawley Gelling, Markus E. Nebel, Benjamin Smith +1
We present a stable mergesort variant, Multiway Powersort, that exploits existing runs and finds nearly-optimal merging orders for k-way merges with negligible overhead. This build…
GAMBIT: The Global and Modular Beyond-the-Standard-Model Inference Tool
The GAMBIT Collaboration, Peter Athron, Csaba Balazs +29
We describe the open-source global fitting package GAMBIT: the Global And Modular Beyond-the-Standard-Model Inference Tool. GAMBIT combines extensive calculations of observables an…
Average Cost of QuickXsort with Pivot Sampling
Sebastian Wild
QuickXsort is a strategy to combine Quicksort with another sorting method X, so that the result has essentially the same comparison cost as X in isolation, but sorts in place even…
Antihelium from Dark Matter
Eric Carlson, Adam Coogan, Tim Linden +3
Cosmic-ray anti-nuclei provide a promising discovery channel for the indirect detection of particle dark matter. Hadron showers produced by the pair-annihilation or decay of Galact…
QuickXsort - A Fast Sorting Scheme in Theory and Practice
Stefan Edelkamp, Armin WeiÃ, Sebastian Wild
QuickXsort is a highly efficient in-place sequential sorting scheme that mixes Hoare's Quicksort algorithm with X, where X can be chosen from a wider range of other known sorting a…
Virtual-Memory Powersort
Finn Moltmann, Tamio-Vesa Nakajima, Sebastian Wild
We give a more space-efficient implementation of adaptive mergesort: Virtual-Memory Powersort. Using internal buffering techniques, we significantly reduce the memory consumption o…
Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees
Meng He, J. Ian Munro, Yakov Nekrich +2
We present the first succinct distance oracles for (unweighted) interval graphs and related classes of graphs, using a novel succinct data structure for ordinal trees that supports…
DarkBit: A GAMBIT module for computing dark matter observables and likelihoods
Torsten Bringmann, Jan Conrad, Jonathan M. Cornell +11
We introduce DarkBit, an advanced software code for computing dark matter constraints on various extensions to the Standard Model of particle physics, comprising both new native co…
Towards Optimal Grammars for RNA Structures
Evarista Onokpasa, Sebastian Wild, Prudence W. H. Wong
In past work (Onokpasa, Wild, Wong, DCC 2023), we showed that (a) for joint compression of RNA sequence and structure, stochastic context-free grammars are the best known compresso…
Exploring light mediators with low-threshold direct detection experiments
Felix Kahlhoefer, Suchita Kulkarni, Sebastian Wild
We explore the potential of future cryogenic direct detection experiments to determine the properties of the mediator that communicates the interactions between dark matter and nuc…
Sesquickselect: One and a half pivots for cache-efficient selection
Conrado MartÃnez, Markus Nebel, Sebastian Wild
Because of unmatched improvements in CPU performance, memory transfers have become a bottleneck of program execution. As discovered in recent years, this also affects sorting in in…
Succinct Permutation Graphs
Konstantinos Tsakalidis, Sebastian Wild, Viktor Zamaraev
We present a succinct data structure for permutation graphs, and their superclass of circular permutation graphs, i.e., data structures using optimal space up to lower order terms.…
Dirac dark matter with a charged mediator: a comprehensive one-loop analysis of the direct detection phenomenology
Alejandro Ibarra, Sebastian Wild
We analyze the direct detection signals of a toy model consisting of a Dirac dark matter particle which couples to one Standard Model fermion via a scalar mediator. For all scenari…
Towards Lazy B-Trees
Casper Moldrup Rysgaard, Sebastian Wild
Lazy search trees (Sandlund & Wild FOCS 2020, Sandlund & Zhang SODA 2022) are sorted dictionaries whose update and query performance smoothly interpolates between that of efficient…
Space-Efficient Hierholzer: Eulerian Cycles in Time and Space
Ziad Ismaili Alaoui, Detlef Plump, Sebastian Wild
We describe a simple variant of Hierholzer's algorithm that finds an Eulerian cycle in a (multi)graph with vertices and edges using bits of working me…
Self-interacting dark matter with a stable vector mediator
Michael Duerr, Kai Schmidt-Hoberg, Sebastian Wild
Light vector mediators can naturally induce velocity-dependent dark matter self-interactions while at the same time allowing for the correct dark matter relic abundance via thermal…
RNA secondary structures: from ab initio prediction to better compression, and back
Evarista Onokpasa, Sebastian Wild, Prudence W. H. Wong
In this paper, we use the biological domain knowledge incorporated into stochastic models for ab initio RNA secondary-structure prediction to improve the state of the art in joint…
Lazy Search Trees
Bryce Sandlund, Sebastian Wild
We introduce the lazy search tree data structure. The lazy search tree is a comparison-based data structure on the pointer machine that supports order-based operations such as rank…
Analysis of Pivot Sampling in Dual-Pivot Quicksort
Sebastian Wild, Markus E. Nebel, Conrado MartÃnez
The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries. They make a basic variant of this a…
Rooting Out Entropy: Optimal Tree Extraction for Ultra-Succinct Graphs
Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Namrata +1
We combine two methods for the lossless compression of unlabeled graphs - entropy compressing adjacency lists and computing canonical names for vertices - and solve an ensuing nove…
Finding the saddlepoint faster than sorting
Justin Dallant, Frederik Haagensen, Riko Jacob +2
A saddlepoint of an matrix is an entry of that is a maximum in its row and a minimum in its column. Knuth (1968) gave several different algorithms for finding…
Higher order dark matter annihilations in the Sun and implications for IceCube
Alejandro Ibarra, Maximilian Totzauer, Sebastian Wild
Dark matter particles captured in the Sun would annihilate producing a neutrino flux that could be detected at the Earth. In some channels, however, the neutrino flux lies in the M…
Why Is Dual-Pivot Quicksort Fast?
Sebastian Wild
I discuss the new dual-pivot Quicksort that is nowadays used to sort arrays of primitive types in Java. I sketch theoretical analyses of this algorithm that offer a possible, and i…
Antideuterons in cosmic rays: sources and discovery potential
Johannes Herms, Alejandro Ibarra, Andrea Vittino +1
Antibaryons are produced in our Galaxy in collisions of high energy cosmic rays with the interstellar medium and in old supernova remnants, and possibly, in exotic sources such as…
BBN constraints on MeV-scale dark sectors. Part I. Sterile decays
Marco Hufnagel, Kai Schmidt-Hoberg, Sebastian Wild
We study constraints from Big Bang Nucleosynthesis on inert particles in a dark sector which contribute to the Hubble rate and therefore change the predictions of the primordial nu…
High-energy neutrino signals from the Sun in dark matter scenarios with internal bremsstrahlung
Alejandro Ibarra, Maximilian Totzauer, Sebastian Wild
We investigate the prospects to observe a high energy neutrino signal from dark matter annihilations in the Sun in scenarios where the dark matter is a Majorana fermion that couple…
Quicksort Is Optimal For Many Equal Keys
Sebastian Wild
I prove that the average number of comparisons for median-of- Quicksort (with fat-pivot a.k.a. three-way partitioning) is asymptotically only a constant times worse than…
Towards the 5/6-Density Conjecture of Pinwheel Scheduling
Leszek GÄ sieniec, Benjamin Smith, Sebastian Wild
Pinwheel Scheduling aims to find a perpetual schedule for unit-length tasks on a single machine subject to given maximal time spans (a.k.a. frequencies) between any two consecutive…
Succinct Euler-Tour Trees
Travis Gagie, Sebastian Wild
We show how a collection of Euler-tour trees for a forest on vertices can be stored in bits such that simple queries take constant time, more complex queries take…
Average Case and Distributional Analysis of Dual-Pivot Quicksort
Sebastian Wild, Markus E. Nebel, Ralph Neininger
In 2009, Oracle replaced the long-serving sorting algorithm in its Java 7 runtime library by a new dual-pivot Quicksort variant due to Vladimir Yaroslavskiy. The decision was based…