Separating Hash Families: A Johnson-type bound and New Constructions

DOI10.1137/15M103827XzbMath1352.05043arXiv1601.04807OpenAlexW2963711761MaRDI QIDQ5298169

Chong Shangguan, Gennian Ge

Publication date: 13 December 2016

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

Full work available at URL: https://arxiv.org/abs/1601.04807

zbMATH Keywords

perfect hash familyrainbow cycleseparating hash family\(R\)-sum-free setJohnson-type bound

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Cryptography (94A60) Other designs, configurations (05B30) Other types of codes (94B60)

Related Items

New upper bounds for parent-identifying codes and traceability codes ⋮ Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings ⋮ Bounds and constructions for \(\overline {3}\)-strongly separable codes with length 3 ⋮ Sparse Hypergraphs with Applications to Coding Theory ⋮ Sparse hypergraphs: new bounds and constructions ⋮ Some intriguing upper bounds for separating hash families ⋮ Constructions and bounds for separating hash families ⋮ Degenerate Turán densities of sparse hypergraphs ⋮ Distributing hash families with few rows

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved bounds for separating hash families
• Uniform hypergraphs containing no grids
• On an extremal hypergraph problem of Brown, Erdős and Sós
• Perfect hash families of strength three with three rows from varieties on finite projective geometries
• A bound on the size of separating hash families
• Explicit constructions for perfect hash families
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• New bounds for perfect hashing via information theory
• On codes with the identifiable parent property
• Generalized hashing and parent-identifying codes.
• Secure frameproof codes, key distribution patterns, group testing algorithms and related structures
• Perfect hash families: Probabilistic methods and explicit constructions
• An upper bound on the size of a code with the \(k\)-identifiable parent property
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Bounds for separating hash families
• On generalized separating hash families
• On the existence of triangulated spheres in 3-graphs, and related problems
• Efficient Multiplicative Sharing Schemes
• Solving a linear equation in a set of integers I
• The Algorithmic Aspects of the Regularity Lemma
• Perfect Hashing and Probability
• Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes
• Frameproof Codes
• Combinatorial properties of frameproof and traceability codes
• New Bounds on Parent-Identifying Codes: The Case of Multiple Parents
• Collusion-secure fingerprinting for digital data
• Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
• Perfect Hash Families: Constructions and Existence
• On coloring graphs to maximize the proportion of multicolored k-edges
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Parent-identifying codes