On the Size of Separating Systems and Families of Perfect Hash Functions

DOI10.1137/0605009zbMath0525.68037OpenAlexW2053816258WikidataQ56021018 ScholiaQ56021018MaRDI QIDQ3038628

János Komlós, Michael L. Fredman

Publication date: 1984

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0605009

zbMATH Keywords

separating systemperfect hash functionminimum size of families of partitions

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorial aspects of partitions of integers (05A17)

Related Items

\(\Sigma\Pi\Sigma\) threshold formulas, On generalizations of separating and splitting families, Information compression and Varshamov-Gilbert bound, Generalised cumulative arrays in secret sharing, Secret sharing schemes with partial broadcast channels, Better lower bounds for monotone threshold formulas, Fredman–Komlós bounds and information theory, On colorful edge triples in edge-colored complete graphs, Separation and Witnesses, Construction of universal enumerators and formulas for threshold functions, New bounds for perfect hashing via information theory, Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Minimal and Monotone Minimal Perfect Hash Functions, Linear Time Constructions of Some $$d$$-Restriction Problems, Perfect hash families of strength three with three rows from varieties on finite projective geometries, Perfect Hashing and Probability, Removing Ramsey theory: Lower bounds with smaller domain size, Approximation of functions of few variables in high dimensions, Entropy of symmetric graphs, Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings, Semi-external LTL Model Checking, Complexity of approximation of functions of few variables in high dimensions, Generalized hashing and parent-identifying codes., New bounds for perfect \(k\)-hashing, Splitting systems and separating systems., Covering complete hypergraphs with cuts of minimum total size, Evolving Perfect Hash Families: A Combinatorial Viewpoint of Evolving Secret Sharing, A note on Ramsey numbers for Berge-\(G\) hypergraphs, Orientations making \(k\)-cycles cyclic, Improved bounds for covering complete uniform hypergraphs, Symmetric graphs with respect to graph entropy, Explicit constructions of perfect hash families from algebraic curves over finite fields, Some bounds of weighted entropies with augmented Zagreb index edge weights, Recursive bounds for perfect hashing, The combinatorics of generalised cumulative arrays, Covering Complete r-Graphs with Spanning Complete r-Partite r-Graphs, A generalization of the Bollobás set pairs inequality, Explicit constructions for perfect hash families, Information based complexity for high dimensional sparse functions, On the Circuit Complexity of Perfect Hashing, Degenerate Turán densities of sparse hypergraphs, Optimal linear perfect hash families, Beating Fredman-Komlós for Perfect k-Hashing., Randomness in secret sharing and visual cryptography schemes, Beating Fredman-Komlós for perfect \(k\)-hashing, The hat guessing number of graphs, Perfect hash families: Probabilistic methods and explicit constructions, Anti-Ramsey colorings in several rounds, On two continuum armed bandit problems in high dimensions

Cites Work

• Should Tables Be Sorted?
• The Complexity of Maintaining an Array and Computing Its Partial Sums