research
∙
08/27/2023
Locally Uniform Hashing
Hashing is a common technique used in data processing, with a strong imp...
share
research
∙
05/04/2023
A Sparse Johnson-Lindenstrauss Transform using Fast Hashing
The Sparse Johnson-Lindenstrauss Transform of Kane and Nelson (SODA 2012...
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...
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
∙
05/17/2022
Improved Utility Analysis of Private CountSketch
Sketching is an important tool for dealing with high-dimensional vectors...
research
∙
05/03/2022
Understanding the Moments of Tabulation Hashing via Chaoses
Simple tabulation hashing dates back to Zobrist in 1970 and is defined a...
research
∙
11/17/2021
Optimal Decremental Connectivity in Non-Sparse Graphs
We present a dynamic algorithm for maintaining the connected and 2-edge-...
research
∙
10/06/2021
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor
We consider the numerical taxonomy problem of fitting a positive distanc...
research
∙
07/08/2021
Sampling and Counting Edges via Vertex Accesses
We consider the problems of sampling and counting edges from a graph on ...
research
∙
04/11/2021
Load Balancing with Dynamic Set of Balls and Bins
In dynamic load balancing, we wish to distribute balls into bins in an e...
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
∙
04/02/2020
No Repetition: Fast Streaming with Highly Concentrated Hashing
To get estimators that work within a certain error bound with high proba...
research
∙
09/24/2019
Random k-out subgraph leaves only O(n/k) inter-component edges
Each vertex of an arbitrary simple graph on n vertices chooses k random ...
research
∙
09/16/2019
Three-in-a-Tree in Near Linear Time
The three-in-a-tree problem is to determine if a simple undirected graph...
research
∙
09/02/2019
Disks in Curves of Bounded Convex Curvature
We say that a simple, closed curve γ in the plane has bounded convex cur...
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
∙
07/04/2019
Hardness of Bichromatic Closest Pair with Jaccard Similarity
Consider collections A and B of red and blue sets, respectively. Bichrom...
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
∙
12/06/2018
Confirmation Sampling for Exact Nearest Neighbor Search
Locality-sensitive hashing (LSH), introduced by Indyk and Motwani in STO...
research
∙
10/31/2018
Non-Empty Bins with Simple Tabulation Hashing
We consider the hashing of a set X⊆ U with |X|=m using a simple tabulati...
research
∙
10/09/2018
Contraction-Based Sparsification in Near-Linear Time
Recently, Kawarabayashi and Thorup presented the first deterministic edg...
research
∙
05/16/2018
Wireless coverage prediction via parametric shortest paths
When deciding where to place access points in a wireless network, it is ...
research
∙
04/25/2018
Power of d Choices with Simple Tabulation
Suppose that we are to place m balls into n bins sequentially using the ...
research
∙
03/31/2018
Fast Fencing
We consider very natural "fence enclosure" problems studied by Capoyleas...
research
∙
11/23/2017
Practical Hash Functions for Similarity Estimation and Dimensionality Reduction
Hashing is a basic tool for dimensionality reduction employed in several...
research
∙
02/05/2007
