research
∙
04/13/2023
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
We revisit Nisan's classical pseudorandom generator (PRG) for space-boun...
share
research
∙
02/12/2023
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Given a simple n-vertex, m-edge graph G undergoing edge insertions and d...
research
∙
11/17/2021
Optimal Decremental Connectivity in Non-Sparse Graphs
We present a dynamic algorithm for maintaining the connected and 2-edge-...
research
∙
08/19/2020
The Power of Hashing with Mersenne Primes
The classic way of computing a k-universal hash function is to use a ran...
research
∙
09/02/2019
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
We provide a simple new randomized contraction approach to the global mi...
research
∙
05/01/2019
Fast hashing with Strong Concentration Bounds
Previous work on tabulation hashing of Pǎtraşcu and Thorup from STOC'11 ...
research
∙
04/25/2018
