Perfect Hashing and Probability

DOI10.1017/S0963548300001280zbMath0820.68063OpenAlexW2035697831MaRDI QIDQ4314156

Noga Alon

Publication date: 20 November 1994

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548300001280

zbMATH Keywords

perfect hash functions

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Signal detection and filtering (aspects of stochastic processes) (60G35)

Related Items (20)

Separating Hash Families: A Johnson-type bound and New Constructions ⋮ Separating systems and oriented graphs of diameter two ⋮ Separation and Witnesses ⋮ Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem ⋮ On separating systems ⋮ Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings ⋮ Bipartite Hansel results for hypergraphs ⋮ Generalized hashing and parent-identifying codes. ⋮ New bounds for perfect \(k\)-hashing ⋮ Some intriguing upper bounds for separating hash families ⋮ Recursive bounds for perfect hashing ⋮ Interval Packing and Covering in the Boolean Lattice ⋮ Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem ⋮ Covering Complete r-Graphs with Spanning Complete r-Partite r-Graphs ⋮ On the Circuit Complexity of Perfect Hashing ⋮ Beating Fredman-Komlós for Perfect k-Hashing. ⋮ Beating Fredman-Komlós for perfect \(k\)-hashing ⋮ On two continuum armed bandit problems in high dimensions

Cites Work

• New bounds for perfect hashing via information theory
• On the Size of Separating Systems and Families of Perfect Hash Functions
• Fredman–Komlós bounds and information theory

This page was built for publication: Perfect Hashing and Probability