47 citations · 80 across the 14 of their papers we have counts for
16 papers
Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row, with Applications
Martin Dietzfelbinger, Stefan Walzer
In this paper we identify a new class of sparse near-quadratic random Boolean matrices that have full row rank over with high probability and can be transfor…
Dense Peelable Random Uniform Hypergraphs
Martin Dietzfelbinger, Stefan Walzer
We describe a new family of -uniform hypergraphs with independent random edges. The hypergraphs have a high probability of being peelable, i.e. to admit no sub-hypergraph of min…
A Subquadratic Algorithm for 3XOR
Martin Dietzfelbinger, Philipp Schlag, Stefan Walzer
Given a set of binary words of equal length , the 3XOR problem asks for three elements such that , where denotes the bitwise XOR…
Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths
Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger +2
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…
A Simple Hash Class with Strong Randomness Properties in Graphs and Hypergraphs
Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel
We study randomness properties of graphs and hypergraphs generated by simple hash functions. Several hashing applications can be analyzed by studying the structure of -uniform r…
Counting Zeros in Random Walks on the Integers and Analysis of Optimal Dual-Pivot Quicksort
Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger +2
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 a…