71 citations · 230 across the 50 of their papers we have counts for
63 papers
Locally Uniform Hashing
Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen +2
Hashing is a common technique used in data processing, with a strong impact on the time and resources spent on computation. Hashing also affects the applicability of theoretical re…
A Sparse Johnson-Lindenstrauss Transform using Fast Hashing
Jakob Bæk Tejs Houen, Mikkel Thorup
The \emph{Sparse Johnson-Lindenstrauss Transform} of Kane and Nelson (SODA 2012) provides a linear dimensionality-reducing map in that pres…
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
Praneeth Kacham, Rasmus Pagh, Mikkel Thorup +1
We revisit Nisan's classical pseudorandom generator (PRG) for space-bounded computation (STOC 1990) and its applications in streaming algorithms. We describe a new generator, HashP…
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Gramoz Goranci, Monika Henzinger, Danupon Nanongkai +3
Given a simple -vertex, -edge graph undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of $G…
Understanding the Moments of Tabulation Hashing via Chaoses
Jakob Bæk Tejs Houen, Mikkel Thorup
Simple tabulation hashing dates back to Zobrist in 1970 and is defined as follows: Each key is viewed as characters from some alphabet , we have fully random hash functi…
Improved Utility Analysis of Private CountSketch
Rasmus Pagh, Mikkel Thorup
Sketching is an important tool for dealing with high-dimensional vectors that are sparse (or well-approximated by a sparse vector), especially useful in distributed, parallel, and…