71 citations · 230 across the 50 of their papers we have counts for
6 papers · 1 filter
Linear Probing with 5-Independent Hashing
Mikkel Thorup
These lecture notes show that linear probing takes expected constant time if the hash function is 5-independent. This result was first proved by Pagh et al. [STOC'07,SICOMP'09]. Th…
Faster Worst Case Deterministic Dynamic Connectivity
Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie +1
We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time and constant…
From Independence to Expansion and Back Again
Tobias Christiani, Rasmus Pagh, Mikkel Thorup
We consider the following fundamental problems: (1) Constructing -independent hash functions with a space-time tradeoff close to Siegel's lower bound. (2) Constructing represent…
Fast and Powerful Hashing using Tabulation
Mikkel Thorup
Randomized algorithms are often enjoyed for their simplicity, but the hash functions employed to yield the desired probabilistic guarantees are often too complicated to be practica…
High Speed Hashing for Integers and Strings
Mikkel Thorup
These notes describe the most efficient hash functions currently known for hashing integers and strings. These modern hash functions are often an order of magnitude faster than tho…
Construction and impromptu repair of an MST in a distributed network with o(m) communication
Valerie King, Shay Kutten, Mikkel Thorup
In the CONGEST model, a communications network is an undirected graph whose nodes are processors and whose edges are the communications links between processors. At any giv…