New bounds for perfect hashing via information theory

DOI10.1016/S0195-6698(88)80048-9zbMATH Open0676.68007OpenAlexW2056884477MaRDI QIDQ1122979FDOQ1122979

Authors: S. H. Smith 

Publication date: 1988

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0195-6698(88)80048-9

Recommendations

• Recursive bounds for perfect hashing
• New bounds for perfect \(k\)-hashing
• Beating Fredman-Komlós for perfect \(k\)-hashing
• Fredman–Komlós bounds and information theory
• Improved bounds for separating hash families

zbMATH Keywords

information theoryperfect hashing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Cites Work

• On the Size of Separating Systems and Families of Perfect Hash Functions
• Fredman–Komlós bounds and information theory
• Title not available (Why is that?)
• Lexicographic codes: Error-correcting codes from game theory
• Title not available (Why is that?)

Cited In (33)

• Optimal linear perfect hash families
• Beating Fredman-Komlós for Perfect k-Hashing.
• Approximation of functions of few variables in high dimensions
• Title not available (Why is that?)
• On the extremal combinatorics of the Hamming space
• On the Circuit Complexity of Perfect Hashing
• Generalized hashing and parent-identifying codes.
• On colorful edge triples in edge-colored complete graphs
• A better bound for locally thin set families
• Some intriguing upper bounds for separating hash families
• New bounds for perfect \(k\)-hashing
• Separating hash families: a Johnson-type bound and new constructions
• Generalizing Körner's graph entropy to graphons
• Beating the probabilistic lower bound on \(q\)-perfect hashing
• On codes with the identifiable parent property
• Recursive bounds for perfect hashing
• Perfect hash families: Probabilistic methods and explicit constructions
• Separation and Witnesses
• Cross‐intersecting couples of graphs
• Beating Fredman-Komlós for perfect \(k\)-hashing
• Anti-Ramsey colorings in several rounds
• Entropy splitting for antiblocking corners and perfect graphs
• Interactive Hashing: An Information Theoretic Tool (Invited Talk)
• Maximum IPP codes of length 3
• Symmetric graphs with respect to graph entropy
• Linear Time Constructions of Some $$d$$-Restriction Problems
• A generalization of the Bollobás set pairs inequality
• Complexity of approximation of functions of few variables in high dimensions
• Perfect Hashing and Probability
• Title not available (Why is that?)
• Entropy of symmetric graphs
• Explicit constructions for perfect hash families
• Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings

This page was built for publication: New bounds for perfect hashing via information theory

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