14 citations · 21 across the 5 of their papers we have counts for
5 papers
Towards Optimal Degree-distributions for Left-perfect Matchings in Random Bipartite Graphs
Martin Dietzfelbinger, Michael Rink
Consider a random bipartite multigraph with left nodes and right nodes. Each left node has random right neighbors. The average left degre…
On Thresholds for the Appearance of 2-cores in Mixed Hypergraphs
Michael Rink
We study thresholds for the appearance of a 2-core in random hypergraphs that are a mixture of a constant number of random uniform hypergraphs each with a linear number of edges bu…
A More Reliable Greedy Heuristic for Maximum Matchings in Sparse Random Graphs
Martin Dietzfelbinger, Hendrik Peilke, Michael Rink
We 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 gra…
Cuckoo Hashing with Pages
Martin Dietzfelbinger, Michael Mitzenmacher, Michael Rink
Although cuckoo hashing has significant applications in both theoretical and practical settings, a relevant downside is that it requires lookups to multiple locations. In many sett…
Tight Thresholds for Cuckoo Hashing via XORSAT
Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher +3
We 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 si…