Universal Hashing via Integer Arithmetic Without Primes, Revisited

DOI10.1007/978-3-319-98355-4_15MaRDI QIDQ6163629zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Universal hashing and \(k\)-wise independent random variables via integer arithmetic without primes
• scientific article; zbMATH DE number 1418345
• Universal hashing and geometric codes
• A caution on universal classes of hash functions
• MMH* with arbitrary modulus is always almost-universal

Cites work

• A read-once branching program lower bound of \({\omega}(2^{n/4})\) for integer multiplication using universal hashing
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Almost random graphs with simple hash functions
• Consequences of Faster Alignment of Sequences
• Cuckoo hashing
• Deterministic dictionaries
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Finding, minimizing, and counting weighted subgraphs
• Higher lower bounds from the 3SUM conjecture
• scientific article; zbMATH DE number 1688393 (Why is no real title available?)
• scientific article; zbMATH DE number 2185600 (Why is no real title available?)
• scientific article; zbMATH DE number 1303598 (Why is no real title available?)
• scientific article; zbMATH DE number 1418345 (Why is no real title available?)
• scientific article; zbMATH DE number 1445340 (Why is no real title available?)
• Making deterministic signatures quickly
• On risks of using cuckoo hashing with simple universal hash classes
• On the \(k\)-independence required by linear probing and minwise independence
• On the power of two-point based sampling
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Pairwise Independence and Derandomization
• Polynomial hash functions are reliable (extended abstract)
• Pseudorandom generators for space-bounded computation
• Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
• Simple Constructions of Almost k-wise Independent Random Variables
• Space-efficient randomized algorithms for k-sum
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Subquadratic algorithms for 3SUM
• Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
• The computational complexity of universal hashing
• Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
• Towards polynomial lower bounds for dynamic problems
• Universal classes of hash functions
• Universal hashing and \(k\)-wise independent random variables via integer arithmetic without primes
• Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes

Cited in

(6)

• The computational complexity of universal hashing
• MMH* with arbitrary modulus is always almost-universal
• On the Minimum Number of Multiplications Necessary for Universal Hash Functions
• Universal hashing and \(k\)-wise independent random variables via integer arithmetic without primes
• Removing additive structure in 3SUM-based reductions
• HalftimeHash: modern hashing without 64-bit multipliers or finite fields

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6163629)