1 citations · 1 across the 5 of their papers we have counts for
7 papers
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…
On Sums of Monotone Random Integer Variables
Anders Aamand, Noga Alon, Jakob Bæk Tejs Knudsen +1
We say that a random integer variable is monotone if the modulus of the characteristic function of is decreasing on . This is the case for many commonly encountered…
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…
Classifying Convex Bodies by their Contact and Intersection Graphs
Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen +1
Suppose that is a convex body in the plane and that are translates of . Such translates give rise to an intersection graph of , , with vertices $…