5 papers · 1 filter
Fast Evaluation of Polynomials with Rational Preprocessing
Thomas D. Ahle, Jakob B. T. Knudsen
Horner's rule evaluates a monic degree- polynomial using multiplications. We show that with rational preprocessing of the coefficients, any such polynomial can be evaluate…
Load Balancing with Dynamic Set of Balls and Bins
Anders Aamand, Jakob Bæk Tejs Knudsen, Mikkel Thorup
In dynamic load balancing, we wish to distribute balls into bins in an environment where both balls and bins can be added and removed. We want to minimize the maximum load of any b…
The Power of Hashing with Mersenne Primes
Thomas Dybdahl Ahle, Jakob Tejs Bæk Knudsen, Mikkel Thorup
The classic way of computing a -universal hash function is to use a random degree- polynomial over a prime field . For a fast computation of the polynomial,…
No Repetition: Fast Streaming with Highly Concentrated Hashing
Anders Aamand, Debarati Das, Evangelos Kipouridis +3
To get estimators that work within a certain error bound with high probability, a common strategy is to design one that works with constant probability, and then boost the probabil…
Fast hashing with Strong Concentration Bounds
Anders Aamand, Jakob B. T. Knudsen, Mathias B. T. Knudsen +2
Previous work on tabulation hashing by Patrascu and Thorup from STOC'11 on simple tabulation and from SODA'13 on twisted tabulation offered Chernoff-style concentration bounds on h…