The EMS Publishing House is now EMS Press and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

Annales de l’Institut Henri Poincaré D


Full-Text PDF (202 KB) | Metadata | Table of Contents | AIHPD summary
Online access to the full text of Annales de l’Institut Henri Poincaré D is restricted to the subscribers of the journal, who are encouraged to communicate their IP-address(es) to their agent or directly to the publisher at
subscriptions@ems-ph.org
Volume 5, Issue 2, 2018, pp. 153–171
DOI: 10.4171/AIHPD/51

Published online: 2018-02-09

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

Aldo Procacci[1] and Remy Sanchis[2]

(1) Universidade Federal de Minas Gerais, Belo Horizonte, Brazil
(2) Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

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.

Keywords: Hash families, algorithmic Lovász local lemma, hard-core lattice gas

Procacci Aldo, Sanchis Remy: Perfect and separating hash families: new bounds via the algorithmic cluster expansion local lemma. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 5 (2018), 153-171. doi: 10.4171/AIHPD/51