Martin Dietzfelbinger
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Martin Dietzfelbinger has a total of 69 co-authors. Here are the top co-authors by number of shared publications:
- Peter Sanders
Karlsruhe Institute of Technology, Karlsruhe, Germany
13 shared publications - Kurt Mehlhorn
Max Planck Institute for Informatics, Saarbrücken, Germany
12 shared publications - Martin Aumüller
IT University of Copenhagen, Copenhagen, Denmark
8 shared publications Michael Rink
Technische Universität Ilmenau
5 shared publications- Philipp Woelfel
Department of Computer Science, University of Calgary, Calgary, Canada
5 shared publications - Michael Rink
Fakultät für Informatik und Automatisierung Technische Universität Ilmenau
4 shared publications
Latest Publications
- Open Access
- 13 February 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 73 (1) , 1-45
Ribbon: Fast Succinct Static Retrieval and Approximate Membership
Given a set \(S \subseteq \mathcal {U}\) and a function \(f:S\rightarrow \lbrace 0,1\rbrace ^r\) , a static retrieval data structure for f supports queries that return \(f(x)\) for \(x \in S\) and an arbitrary value from \(\lbrace 0,1\rbrace ^r\) for \(x \in \mathcal {U}\setminus S\) . Retrieval data structures can be used to implement a static approximate membership query (AMQ) data structure, i.e., a Bloom filter alternative, with false positive rate \(2^{-r}\) . The information-theoretic space lower bound for both tasks is \(r|S|\) bits, and here we aim to use space \(r|S|(1+\varepsilon)\) bits for a small overhead \(\varepsilon\) , including succinct constructions with \(\varepsilon = o(1)\) . A well-known approach to this task associates each key \(x \in S\) with a row vector \(\smash{\vec{h}}(x) \in \lbrace 0,1\rbrace ^{m}\) and stores a matrix \(Z\in \lbrace 0,1\rbrace ^{m\times r}\) such that \(\smash{\vec{h}}(x)\cdot Z = f(x)\) for every \(x \in S\) . We propose a new variant where \(\smash{\vec{h}}(x)\) contains a short block of random bits at a random position \(s(x)\) , and is otherwise zero. Sorting the row vectors by \(s(x)\) gives a matrix \(A \in \lbrace 0,1\rbrace ^{n \times m}\) with non-zero entries concentrated in a “ribbon” along a generalized diagonal. This makes a variant of Gaussian elimination particularly efficient at computing Z . We thus obtain simple data structures called Standard Ribbon Retrieval and Homogeneous Ribbon Filter . We then refine the construction using bumping (a variant of backyarding) and overloading (using \(m \lt n\) ) to obtain bumped ribbon retrieval (“BuRR”), with overhead \(\mathcal {O}\!(\frac{\log w}{rw^2})\) , query time \(\mathcal {O}\!(1+\frac{rw}{\log n})\) , and expected construction time \(\mathcal {O}\!\left(nw\right)\) , for a tuning parameter \(w=\mathcal {O}\!\left(\log n\right)\) that opens a trade-off between space and running time. Our experiments reveal our implementations to be the first to simultaneously achieve small overheads and fast running times in practice, with BuRR achieving overheads well below 1 % while being faster than most competitors, which have larger space overheads. This efficiency, including favorable constants, stems from a combination of simplicity, word parallelism, and high locality. We offer a unified theoretical perspective on these three ribbon-based data structures, including a nontrivial rigorous analysis of their running times and memory consumption.- 13 February 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 73 (1) , 1-45
Open AccessRibbon: Fast Succinct Static Retrieval and Approximate Membership
Given a set \(S \subseteq \mathcal {U}\) and a function \(f:S\rightarrow \lbrace 0,1\rbrace ^r\) , a static retrieval data structure for f supports queries that return \(f(x)\) for \(x \in S\) and an arbitrary value from \(\lbrace 0,1\rbrace ^r\) for \(x \in \mathcal {U}\setminus S\) . Retrieval data structures can be used to implement a static approximate membership query (AMQ) data structure, i.e., a Bloom filter alternative, with false positive rate \(2^{-r}\) . The information-theoretic space lower bound for both tasks is \(r|S|\) bits, and here we aim to use space \(r|S|(1+\varepsilon)\) bits for a small overhead \(\varepsilon\) , including succinct constructions with \(\varepsilon = o(1)\) . A well-known approach to this task associates each key \(x \in S\) with a row vector \(\smash{\vec{h}}(x) \in \lbrace 0,1\rbrace ^{m}\) and stores a matrix \(Z\in \lbrace 0,1\rbrace ^{m\times r}\) such that \(\smash{\vec{h}}(x)\cdot Z = f(x)\) for every \(x \in S\) . We propose a new variant where \(\smash{\vec{h}}(x)\) contains a short block of random bits at a random position \(s(x)\) , and is otherwise zero. Sorting the row vectors by \(s(x)\) gives a matrix \(A \in \lbrace 0,1\rbrace ^{n \times m}\) with non-zero entries concentrated in a “ribbon” along a generalized diagonal. This makes a variant of Gaussian elimination particularly efficient at computing Z . We thus obtain simple data structures called Standard Ribbon Retrieval and Homogeneous Ribbon Filter . We then refine the construction using bumping (a variant of backyarding) and overloading (using \(m \lt n\) ) to obtain bumped ribbon retrieval (“BuRR”), with overhead \(\mathcal {O}\!(\frac{\log w}{rw^2})\) , query time \(\mathcal {O}\!(1+\frac{rw}{\log n})\) , and expected construction time \(\mathcal {O}\!\left(nw\right)\) , for a tuning parameter \(w=\mathcal {O}\!\left(\log n\right)\) that opens a trade-off between space and running time. Our experiments reveal our implementations to be the first to simultaneously achieve small overheads and fast running times in practice, with BuRR achieving overheads well below 1 % while being faster than most competitors, which have larger space overheads. This efficiency, including favorable constants, stems from a combination of simplicity, word parallelism, and high locality. We offer a unified theoretical perspective on these three ribbon-based data structures, including a nontrivial rigorous analysis of their running times and memory consumption. - 14 August 2018
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 28 (4) , 485-518
Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths
We present an average-case analysis of a variant of dual-pivot quicksort. We show that the algorithmic partitioning strategy used is optimal, that is, it minimizes the expected number of key comparisons. For the analysis, we calculate the expected number of comparisons exactly as well as asymptotically; in particular, we provide exact expressions for the linear, logarithmic and constant terms.An essential step is the analysis of zeros of lattice paths in a certain probability model. Along the way a combinatorial identity is proved.
- 14 August 2018
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 28 (4) , 485-518
Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths
We present an average-case analysis of a variant of dual-pivot quicksort. We show that the algorithmic partitioning strategy used is optimal, that is, it minimizes the expected number of key comparisons. For the analysis, we calculate the expected number of comparisons exactly as well as asymptotically; in particular, we provide exact expressions for the linear, logarithmic and constant terms.An essential step is the analysis of zeros of lattice paths in a certain probability model. Along the way a combinatorial identity is proved.
- 9 August 2018
- Published by Springer Nature
- p. 257-279
Universal Hashing via Integer Arithmetic Without Primes, Revisited
- 9 August 2018
- Published by Springer Nature
- p. 257-279
Universal Hashing via Integer Arithmetic Without Primes, Revisited
- Open Access
A Subquadratic Algorithm for 3XOR
Given a set $X$ of $n$ binary words of equal length $w$, the 3XOR problem asks for three elements $a, b, c \in X$ such that $a \oplus b=c$, where $ \oplus$ denotes the bitwise XOR operation. The problem can be easily solved on a word RAM with word length $w$ in time $O(n^2 \log{n})$. Using Han's fast integer sorting algorithm (2002/2004) this can be reduced to $O(n^2 \log{\log{n}})$. With randomization or a sophisticated deterministic dictionary construction, creating a hash table for $X$ with constant lookup time leads to an algorithm with (expected) running time $O(n^2)$. At present, seemingly no faster algorithms are known. We present a surprisingly simple deterministic, quadratic time algorithm for 3XOR. Its core is a version of the Patricia trie for $X$, which makes it possible to traverse the set $a \oplus X$ in ascending order for arbitrary $a\in \{0, 1\}^{w}$ in linear time. Furthermore, we describe a randomized algorithm for 3XOR with expected running time $O(n^2\cdot\min\{\log^3{w}/w, (\log\log{n})^2/\log^2 n\})$. The algorithm transfers techniques to our setting that were used by Baran, Demaine, and P\u{a}tra\c{s}cu (2005/2008) for solving the related int3SUM problem (the same problem with integer addition in place of binary XOR) in expected time $o(n^2)$. As suggested by Jafargholi and Viola (2016), linear hash functions are employed. The latter authors also showed that assuming 3XOR needs expected running time $n^{2-o(1)}$ one can prove conditional lower bounds for triangle enumeration just as with 3SUM. We demonstrate that 3XOR can be reduced to other problems as well, treating the examples offline SetDisjointness and offline SetIntersection, which were studied for 3SUM by Kopelowitz, Pettie, and Porat (2016).Open AccessA Subquadratic Algorithm for 3XOR
Given a set $X$ of $n$ binary words of equal length $w$, the 3XOR problem asks for three elements $a, b, c \in X$ such that $a \oplus b=c$, where $ \oplus$ denotes the bitwise XOR operation. The problem can be easily solved on a word RAM with word length $w$ in time $O(n^2 \log{n})$. Using Han's fast integer sorting algorithm (2002/2004) this can be reduced to $O(n^2 \log{\log{n}})$. With randomization or a sophisticated deterministic dictionary construction, creating a hash table for $X$ with constant lookup time leads to an algorithm with (expected) running time $O(n^2)$. At present, seemingly no faster algorithms are known. We present a surprisingly simple deterministic, quadratic time algorithm for 3XOR. Its core is a version of the Patricia trie for $X$, which makes it possible to traverse the set $a \oplus X$ in ascending order for arbitrary $a\in \{0, 1\}^{w}$ in linear time. Furthermore, we describe a randomized algorithm for 3XOR with expected running time $O(n^2\cdot\min\{\log^3{w}/w, (\log\log{n})^2/\log^2 n\})$. The algorithm transfers techniques to our setting that were used by Baran, Demaine, and P\u{a}tra\c{s}cu (2005/2008) for solving the related int3SUM problem (the same problem with integer addition in place of binary XOR) in expected time $o(n^2)$. As suggested by Jafargholi and Viola (2016), linear hash functions are employed. The latter authors also showed that assuming 3XOR needs expected running time $n^{2-o(1)}$ one can prove conditional lower bounds for triangle enumeration just as with 3SUM. We demonstrate that 3XOR can be reduced to other problems as well, treating the examples offline SetDisjointness and offline SetIntersection, which were studied for 3SUM by Kopelowitz, Pettie, and Porat (2016). - Open Access
Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths
We present an average case analysis of a variant of dual-pivot quicksort. We show that the used algorithmic partitioning strategy is optimal, i.e., it minimizes the expected number of key comparisons. For the analysis, we calculate the expected number of comparisons exactly as well as asymptotically, in particular, we provide exact expressions for the linear, logarithmic, and constant terms. An essential step is the analysis of zeros of lattice paths in a certain probability model. Along the way a combinatorial identity is proven.
Open AccessDual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths
We present an average case analysis of a variant of dual-pivot quicksort. We show that the used algorithmic partitioning strategy is optimal, i.e., it minimizes the expected number of key comparisons. For the analysis, we calculate the expected number of comparisons exactly as well as asymptotically, in particular, we provide exact expressions for the linear, logarithmic, and constant terms. An essential step is the analysis of zeros of lattice paths in a certain probability model. Along the way a combinatorial identity is proven.
- Open Access
- 10 October 2016
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 13 (1) , 1-47
How Good Is Multi-Pivot Quicksort?
Multi-Pivot Quicksort refers to variants of classical quicksort where in the partitioning step k pivots are used to split the input into k + 1 segments. For many years, multi-pivot quicksort was regarded as impractical, but in 2009 a two-pivot approach by Yaroslavskiy, Bentley, and Bloch was chosen as the standard sorting algorithm in Sun’s Java 7. In 2014 at ALENEX, Kushagra et al. introduced an even faster algorithm that uses three pivots. This article studies what possible advantages multi-pivot quicksort might offer in general. The contributions are as follows: Natural comparison-optimal algorithms for multi-pivot quicksort are devised and analyzed. The analysis shows that the benefits of using multiple pivots with respect to the average comparison count are marginal and these strategies are inferior to simpler strategies such as the well-known median-of- k approach. A substantial part of the partitioning cost is caused by rearranging elements. A rigorous analysis of an algorithm for rearranging elements in the partitioning step is carried out, observing mainly how often array cells are accessed during partitioning. The algorithm behaves best if three to five pivots are used. Experiments show that this translates into good cache behavior and is closest to predicting observed running times of multi-pivot quicksort algorithms. Finally, it is studied how choosing pivots from a sample affects sorting cost. The study is theoretical in the sense that although the findings motivate design recommendations for multipivot quicksort algorithms that lead to running-time improvements over known algorithms in an experimental setting, these improvements are small.
- 10 October 2016
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 13 (1) , 1-47
Open AccessHow Good Is Multi-Pivot Quicksort?
Multi-Pivot Quicksort refers to variants of classical quicksort where in the partitioning step k pivots are used to split the input into k + 1 segments. For many years, multi-pivot quicksort was regarded as impractical, but in 2009 a two-pivot approach by Yaroslavskiy, Bentley, and Bloch was chosen as the standard sorting algorithm in Sun’s Java 7. In 2014 at ALENEX, Kushagra et al. introduced an even faster algorithm that uses three pivots. This article studies what possible advantages multi-pivot quicksort might offer in general. The contributions are as follows: Natural comparison-optimal algorithms for multi-pivot quicksort are devised and analyzed. The analysis shows that the benefits of using multiple pivots with respect to the average comparison count are marginal and these strategies are inferior to simpler strategies such as the well-known median-of- k approach. A substantial part of the partitioning cost is caused by rearranging elements. A rigorous analysis of an algorithm for rearranging elements in the partitioning step is carried out, observing mainly how often array cells are accessed during partitioning. The algorithm behaves best if three to five pivots are used. Experiments show that this translates into good cache behavior and is closest to predicting observed running times of multi-pivot quicksort algorithms. Finally, it is studied how choosing pivots from a sample affects sorting cost. The study is theoretical in the sense that although the findings motivate design recommendations for multipivot quicksort algorithms that lead to running-time improvements over known algorithms in an experimental setting, these improvements are small.
- Open Access
Counting Zeros in Random Walks on the Integers and Analysis of Optimal Dual-Pivot Quicksort
We present an average case analysis of two variants of dual-pivot quicksort, one with a non-algorithmic comparison-optimal partitioning strategy, the other with a closely related algorithmic strategy. For both we calculate the expected number of comparisons exactly as well as asymptotically, in particular, we provide exact expressions for the linear, logarithmic, and constant terms. An essential step is the analysis of zeros of lattice paths in a certain probability model. Along the way a combinatorial identity is proven.
Open AccessCounting Zeros in Random Walks on the Integers and Analysis of Optimal Dual-Pivot Quicksort
We present an average case analysis of two variants of dual-pivot quicksort, one with a non-algorithmic comparison-optimal partitioning strategy, the other with a closely related algorithmic strategy. For both we calculate the expected number of comparisons exactly as well as asymptotically, in particular, we provide exact expressions for the linear, logarithmic, and constant terms. An essential step is the analysis of zeros of lattice paths in a certain probability model. Along the way a combinatorial identity is proven.
- Open Access
- 17 November 2015
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 12 (2) , 1-36
Optimal Partitioning for Dual-Pivot Quicksort
Dual-pivot quicksort refers to variants of classical quicksort where in the partitioning step two pivots are used to split the input into three segments. This can be done in different ways, giving rise to different algorithms. Recently, a dual-pivot algorithm due to Yaroslavskiy received much attention, because it replaced the well-engineered quicksort algorithm in Oracle’s Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses 1.9 n ln n + O ( n ) comparisons to sort an input of size n , beating standard quicksort, which uses 2 n ln n + O ( n ) comparisons. We introduce a model that captures all dual-pivot algorithms, give a unified analysis, and identify new dual-pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to a linear term. This minimum is 1.8 n ln n + O ( n ). For the case that the pivots are chosen from a small sample, we include a comparison of dual-pivot quicksort and classical quicksort. Specifically, we show that dual-pivot quicksort benefits from a skewed choice of pivots. We experimentally evaluate our algorithms and compare them to Yaroslavskiy’s algorithm and the recently described 3-pivot quicksort algorithm of Kushagra et al. (ALENEX 2014).
- 17 November 2015
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 12 (2) , 1-36
Open AccessOptimal Partitioning for Dual-Pivot Quicksort
Dual-pivot quicksort refers to variants of classical quicksort where in the partitioning step two pivots are used to split the input into three segments. This can be done in different ways, giving rise to different algorithms. Recently, a dual-pivot algorithm due to Yaroslavskiy received much attention, because it replaced the well-engineered quicksort algorithm in Oracle’s Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses 1.9 n ln n + O ( n ) comparisons to sort an input of size n , beating standard quicksort, which uses 2 n ln n + O ( n ) comparisons. We introduce a model that captures all dual-pivot algorithms, give a unified analysis, and identify new dual-pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to a linear term. This minimum is 1.8 n ln n + O ( n ). For the case that the pivots are chosen from a small sample, we include a comparison of dual-pivot quicksort and classical quicksort. Specifically, we show that dual-pivot quicksort benefits from a skewed choice of pivots. We experimentally evaluate our algorithms and compare them to Yaroslavskiy’s algorithm and the recently described 3-pivot quicksort algorithm of Kushagra et al. (ALENEX 2014).
- 1 September 2015
- Published by Elsevier in Information Processing Letters
- Vol. 115 (9) , 684-688
On testing single connectedness in directed graphs and some related problems
- 1 September 2015
- Published by Elsevier in Information Processing Letters
- Vol. 115 (9) , 684-688
On testing single connectedness in directed graphs and some related problems
- 27 August 2015
- Published by Springer Nature in Theory of Computing Systems
- Vol. 58 (4) , 503-505
Preface of STACS 2013 Special Issue
- 27 August 2015
- Published by Springer Nature in Theory of Computing Systems
- Vol. 58 (4) , 503-505
Preface of STACS 2013 Special Issue