Publications

Martin Dietzfelbinger, Michael Rink
Towards Optimal Degree Distributions for LeftPerfect Matchings in Random Bipartite Graphs
Theory Comput. Syst.
2015:
593 – 611
paper [➚], abstractConsider a random bipartite multigraph $G$ with $n$ left nodes and $m \geq n\geq2$
right nodes. Each left node $x$ has $d_x\geq1$ random right neighbors.
The average left degree $\mean$ is fixed, $\mean\geq2$.
We ask whether for the probability that $G$ has a leftperfect matching
[…] [1.4KiB]

Michael Rink
Thresholds for Matchings in Random Bipartite Graphs with Applications to HashingBased Data Structures
Thesis
2014
paper [1.9MiB], abstractWe study randomized algorithms that take as input a set S of n keys from some large universe U
or a set of n keyvalue pairs, associating each key from S with a specific value, and build
a data structure that solves one of the following tasks. On calling the operation lookup for a key x from U:
* Decide set membership with respect to S (membership tester).
[…] [2.3KiB], cover [101.4KiB], slides [1.2MiB]

Michael Rink
Mixed Hypergraphs for LinearTime Construction of Denser HashingBased Data Structures
Proc. 39th SOFSEM
2013:
356 – 368
paper [➚], abstractThere are several hashingbased data structures whose space utilization (keys per table cells) directly
depends on the edge density threshold for the appearance of a $2$core in some underlying random $k$uniform hypergraph.
We show that by modifying these data structures such that the $k$uniform hypergraphs are replaced
by certain nonuniform hypergraphs their space utilization can be improved.
[…] [942B], extended version (arXiv) [➚], slides [590.3KiB]
superseded by thesis

Martin Dietzfelbinger and Michael Rink
Towards Optimal DegreeDistributions for LeftPerfect Matchings in Random Bipartite Graphs
Proc. 7th CSR
2012:
99 – 111
paper [➚], abstractConsider a random bipartite multigraph $\graph$ with $\keys$ left nodes and $\cells \geq \keys\geq2$
right nodes. Each left node $x$ has $\degr_x\geq1$ random right neighbors.
The average left degree $\Amean$ is fixed, $\Amean\geq2$.
We ask whether for the probability that $\graph$ has a leftperfect matching
[…] [1.5KiB], extended version (arXiv) [➚], slides [712.5KiB]
superseded by journal version

Martin Dietzfelbinger, Hendrik Peilke, Michael Rink
A More Reliable Greedy Heuristic for Maximum Matchings in Sparse Random Graphs
Proc. 11th SEA
2012:
148 – 159
paper [➚], abstractWe propose a new greedy algorithm for the maximum cardinality matching problem. We give
experimental evidence that this algorithm is likely to find a maximum matching in random
graphs with constant expected degree $c>0$, independent of the value of $c$.
This is contrary to the behavior of commonly used greedy matching heuristics which are known
[…] [430B], extended version (arXiv) [➚], slides [1.3MiB]

Martin Dietzfelbinger and Michael Mitzenmacher and Michael Rink
Cuckoo Hashing with Pages
Proc. 19th ESA
2011:
615 – 627
paper [➚], abstractA downside of cuckoo hashing is that it requires lookups to multiple locations, making it a less compelling alternative
when lookups are expensive. One such setting is when memory is arranged in large pages,
and the major cost is the number of page accesses.
We propose the study of cuckoo hashing with pages, advocating approaches
[…] [896B], extended version (arXiv) [➚], slides [793KiB]

Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink
Tight Thresholds for Cuckoo Hashing via XORSAT
Proc. 37th ICALP (1)
2010:
213 – 225
paper [➚], abstractWe settle the question of tight thresholds for offline cuckoo hashing.
The problem can be stated as follows: we have $n$ keys to be hashed
into $m$ buckets each capable of holding a single key.
Each key has $k \geq 3 $ (distinct) associated buckets
[…] [1.3KiB], extended version (arXiv) [➚],
talk at 60. Theorietag

Martin Aumüller, Martin Dietzfelbinger, Michael Rink
Experimental Variations of a Theoretically Good Retrieval Data Structure
Proc. 17th ESA
2009:
742 – 751
paper [➚], abstractA retrieval data structure implements a mapping from a set $S$ of $n$ keys to range $R=\{0,1\}^r$, e.g.
given by a list of keyvalue pairs $(x,v)\in S\times R$, but an element outside $S$ may be mapped to any value.
Asymptotically, minimal perfect hashing allows to build such a data structure that needs
$n\log_2 e + nr+ o(n)$ bits of memory and has constant evaluation time.
[…] [736B], slides [501.9KiB]

Martin Dietzfelbinger, Michael Rink
Applications of a Splitting Trick
Proc. 36th ICALP (1)
2009:
354 – 365
paper [➚], abstractWe study applications of a simple method for circumventing the
``full randomness assumption'' when building
a hashingbased data structure for a set $S$ of keys.
The general approach is to ``split'' $S$ into ``pieces'' $S_i$,
[…] [1.1KiB], slides [166KiB]
Talks

Matchings in Random Bipartite Graphs with Applications to Hashingbased Data Structures
Oberseminar, Lehrstuhl für Theoretische Informatik I, FSU Jena
2012
slides [898.2KiB]
superseded by thesis talk

On Very Space Efficient Hash Tables
Annual Meeting of SPP 1307 Algorithm Engineering, MLU HalleWittenberg
2010
slides [503.2KiB]

Tight Tresholds for Cuckoo Hashing via XORSAT
60. Workshop über Algorithmen und Komplexität (Theorietag), CAU Kiel
2010
slides [439.4KiB]