On the Size of Separating Systems and Families of Perfect Hash Functions
From MaRDI portal
Publication:3038628
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
Related Items (49)
\(\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
This page was built for publication: On the Size of Separating Systems and Families of Perfect Hash Functions
