Polynomial hash functions are reliable

DOI10.1007/3-540-55719-9_77zbMath1425.68098OpenAlexW1576564521MaRDI QIDQ5204320

Joseph (Yossi) Gil, Yossi Matias, Martin Dietzfelbinger, Nicholas J. Pippenger

Publication date: 4 December 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55719-9_77

zbMATH Keywords

finite fieldhash functionuniversal classhigh-degree polynomialprogram size

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20)

Related Items

Compressed string dictionary search with edit distance one, Perfect hashing, Graphs, hypergraphs and hashing, Universal Hashing via Integer Arithmetic Without Primes, Revisited, Simple fast parallel hashing, Optimal Las Vegas reduction from one-way set reconciliation to error correction, Cuckoo hashing: Further analysis, Quantum key distribution using universal hash functions over finite fields, Optimal bounds for the predecessor problem and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
• How to emulate shared memory
• A complexity theory of efficient parallel algorithms
• Two results on tables
• On the power of two-point based sampling
• New hash functions and their use in authentication and set equality
• Universal classes of hash functions
• On a set of almost deterministic k-independent random variables
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Parallel hashing
• Should Tables Be Sorted?
• Dynamic Perfect Hashing: Upper and Lower Bounds