Universal Hashing via Integer Arithmetic Without Primes, Revisited

DOI10.1007/978-3-319-98355-4_15zbMath1514.68043OpenAlexW2885144874MaRDI QIDQ6163629

Martin Dietzfelbinger

Publication date: 30 June 2023

Published in: Adventures Between Lower Bounds and Higher Altitudes (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-98355-4_15

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (1)

HalftimeHash: modern hashing without 64-bit multipliers or finite fields

Cites Work

• Explicit and efficient hash families suffice for cuckoo hashing with a stash
• Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
• On the power of two-point based sampling
• Pseudorandom generators for space-bounded computation
• The computational complexity of universal hashing
• Universal classes of hash functions
• Subquadratic algorithms for 3SUM
• Deterministic Dictionaries
• Finding, Minimizing, and Counting Weighted Subgraphs
• Towards polynomial lower bounds for dynamic problems
• Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation
• Space-Efficient Randomized Algorithms for K-SUM
• Making deterministic signatures quickly
• Pairwise Independence and Derandomization
• Almost random graphs with simple hash functions
• Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
• Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Simple Constructions of Almost k-wise Independent Random Variables
• Dynamic Perfect Hashing: Upper and Lower Bounds
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• Higher Lower Bounds from the 3SUM Conjecture
• Universal hashing and k-wise independent random variables via integer arithmetic without primes
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Cuckoo hashing
• On the k -Independence Required by Linear Probing and Minwise Independence
• Consequences of Faster Alignment of Sequences
• A read-once branching program lower bound of Ω(2 ^n/4 ) for integer multiplication using universal hashing
• Polynomial hash functions are reliable
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Universal Hashing via Integer Arithmetic Without Primes, Revisited