Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma (Q1645018)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6896945
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma |
scientific article; zbMATH DE number 6896945 |
Statements
Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma (English)
0 references
28 June 2018
0 references
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.
0 references
Hash families
0 references
algorithmic Lovász local lemma
0 references
hard-core lattice gas
0 references
0.9131082
0 references
0.90910727
0 references
0.9053307
0 references
0.90444267
0 references
0.90416753
0 references
0.9006374
0 references
0.9002819
0 references
0 references
0.89691705
0 references
