Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma
Annales de l’Institut Henri Poincaré D, Tome 5 (2018) no. 2, pp. 153-171.

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.

Accepté le :
Publié le :
DOI : 10.4171/aihpd/51
Classification : 05-XX, 68-XX, 82-XX, 94-XX
Mots-clés : Hash families, algorithmic Lovász local lemma, hard-core lattice gas 
@article{AIHPD_2018__5_2_153_0,
     author = {Procacci, Aldo and Sanchis, Remy},
     title = {Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma},
     journal = {Annales de l{\textquoteright}Institut Henri Poincar\'e D},
     pages = {153--171},
     volume = {5},
     number = {2},
     year = {2018},
     doi = {10.4171/aihpd/51},
     mrnumber = {3813213},
     zbl = {1391.05253},
     language = {en},
     url = {http://archive.numdam.org/articles/10.4171/aihpd/51/}
}
TY  - JOUR
AU  - Procacci, Aldo
AU  - Sanchis, Remy
TI  - Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma
JO  - Annales de l’Institut Henri Poincaré D
PY  - 2018
SP  - 153
EP  - 171
VL  - 5
IS  - 2
UR  - http://archive.numdam.org/articles/10.4171/aihpd/51/
DO  - 10.4171/aihpd/51
LA  - en
ID  - AIHPD_2018__5_2_153_0
ER  - 
%0 Journal Article
%A Procacci, Aldo
%A Sanchis, Remy
%T Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma
%J Annales de l’Institut Henri Poincaré D
%D 2018
%P 153-171
%V 5
%N 2
%U http://archive.numdam.org/articles/10.4171/aihpd/51/
%R 10.4171/aihpd/51
%G en
%F AIHPD_2018__5_2_153_0
Procacci, Aldo; Sanchis, Remy. Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma. Annales de l’Institut Henri Poincaré D, Tome 5 (2018) no. 2, pp. 153-171. doi : 10.4171/aihpd/51. http://archive.numdam.org/articles/10.4171/aihpd/51/

Cité par Sources :