Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma

DOI10.4171/AIHPD/51MaRDI QIDQ1645018zbMATH OpenWikidataFDO

Authors Aldo Procacci, Rémy Sanchis

Publication date 28 June 2018

Published in Annales de l'Institut Henri Poincaré D. Combinatorics, Physics and their Interactions (AIHPD) (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic Lovász local lemmahard-core lattice gasHash families

Mathematics Subject Classification ID

Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Randomized algorithms (68W20) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Cryptography (94A60)

Abstract: We present new lower bounds for the size of perfect and separating hash families ensuring their existence. Such new bounds are based on the algorithmic Cluster expansion improved version of the Lov'asz Local Lemma, which also implies that the Moser-Tardos algorithm finds such hash families in polynomial time.

Review text

Summary: We present new lower bounds for the size of perfect and separating hash families ensuring their existence. Such new bounds are based on the algorithmic cluster expansion improved version of the Lovász local lemma, which also implies that the Moser-Tardos algorithm finds such hash families in polynomial time.

Recommendations

• A new lower bound on perfect hash families
• A tight bound on the size of certain separating hash families
• Constructions and bounds for separating hash families
• Separating hash families: a Johnson-type bound and new constructions
• A bound on the size of separating hash families
• Improved bounds on the size of separating hash families of short length
• Improved bounds for separating hash families
• New bounds for perfect \(k\)-hashing
• Some intriguing upper bounds for separating hash families
• Perfect hash families: Probabilistic methods and explicit constructions

Cited in

(3)

• Entropy compression versus Lovász local lemma
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• A new lower bound on perfect hash families

This page was built for publication: Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma

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