Polynomial hash functions are reliable (extended abstract)

DOI10.1007/3-540-55719-9_77MaRDI QIDQ5204320zbMATH OpenOpenAlexFDO

Authors Martin Dietzfelbinger, Joseph (Yossi) Gil, Y. Matias, Nicholas 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 functionhigh-degree polynomialprogram sizeuniversal class

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20)

Recommendations

• Minimal perfect hashing in polynomial time
• scientific article; zbMATH DE number 177800
• A caution on universal classes of hash functions
• Collections of Functions for Perfect Hashing
• scientific article; zbMATH DE number 1418345

Cites work

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

Cited in

(17)

• Cuckoo hashing: Further analysis
• Perfect hashing
• Optimal bounds for the predecessor problem and related problems
• The circulant hash revisited
• Quantum key distribution using universal hash functions over finite fields
• Compressed string dictionary search with edit distance one
• Relational Hash: Probabilistic Hash for Verifying Relations, Secure Against Forgery and More
• Multivariates Polynomials for Hashing
• Simple fast parallel hashing
• Optimal Las Vegas reduction from one-way set reconciliation to error correction
• Graphs, hypergraphs and hashing
• Universal Hashing via Integer Arithmetic Without Primes, Revisited
• Sparse suffix and LCP array: simple, direct, small, and fast
• Polynomial hashing over prime order fields
• On the complexity of computing the co-lexicographic width of a regular language
• Locally consistent parsing for text indexing in small space
• Sparse suffix and LCP array: simple, direct, small, and fast

This page was built for publication: Polynomial hash functions are reliable (extended abstract)

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