4 citations · 7 across the 13 of their papers we have counts for
5 papers · 1 filter
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…
Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids
Martin Dietzfelbinger, Philipp Woelfel
We consider Kleinberg's celebrated small world graph model (Kleinberg, 2000), in which a D-dimensional grid {0,...,n-1}^D is augmented with a constant number of additional unidirec…
Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash
Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel
It is shown that for cuckoo hashing with a stash as proposed by Kirsch, Mitzenmacher, and Wieder (2008) families of very simple hash functions can be used, maintaining the favorabl…
Independence of Tabulation-Based Hash Classes
Toryn Qwyllyn Klassen, Philipp Woelfel
A tabulation-based hash function maps a key into d derived characters indexing random values in tables that are then combined with bitwise xor operations to give the hash. Thorup a…
Tight Bounds for Blind Search on the Integers
Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener +1
We analyze a simple random process in which a token is moved in the interval μ\{1,...,n$. Initially, the token is placed in…