39 citations · 76 across the 11 of their papers we have counts for
Showing 2010Show all
3 papers · 1 filter
cs.DS2010★ 1 cited
The Power of Simple Tabulation Hashing
Mihai Patrascu, Mikkel Thorup
Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here w…
cs.DS2010★ 16 cited
Unifying the Landscape of Cell-Probe Lower Bounds
Mihai Patrascu
We show that a large fraction of the data-structure lower bounds known today in fact follow by reduction from the communication complexity of lopsided (asymmetric) set disjointness…
cs.DS2010
Transdichotomous Results in Computational Geometry, II: Offline Search
Timothy M. Chan, Mihai Patrascu
We reexamine fundamental problems from computational geometry in the word RAM model, where input coordinates are integers that fit in a machine word. We develop a new algorithm for…