In this paper we study the hard sphere packing problem in the Hamming space by the cavity method. We show that both the replica symmetric and the replica symmetry breaking approximations give maximum rates of packing that are asymptotically the same as the lower bound of Gilbert and Varshamov. Consistently with known numerical results, the replica symmetric equations also suggest a crystalline solution, where for even diameters the spheres are more likely to be found in one of the subspaces (even or odd) of the Hamming space. These crystalline packings can be generated by a recursive algorithm which finds maximum packings in an ultrametric space. Finally, we design a message passing algorithm based on the cavity equations to find dense packings of hard spheres. Known maximum packings are reproduced efficiently in nontrivial ranges of dimensions and number of spheres.

Cavity approach to sphere packing in Hamming space / Ramezanpour, Abolfazl; Zecchina, Riccardo. - In: PHYSICAL REVIEW E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS. - ISSN 1539-3755. - STAMPA. - 85:(2012), pp. 021106-021106. [10.1103/PhysRevE.85.021106]

Cavity approach to sphere packing in Hamming space

RAMEZANPOUR, ABOLFAZL;ZECCHINA, RICCARDO
2012

Abstract

In this paper we study the hard sphere packing problem in the Hamming space by the cavity method. We show that both the replica symmetric and the replica symmetry breaking approximations give maximum rates of packing that are asymptotically the same as the lower bound of Gilbert and Varshamov. Consistently with known numerical results, the replica symmetric equations also suggest a crystalline solution, where for even diameters the spheres are more likely to be found in one of the subspaces (even or odd) of the Hamming space. These crystalline packings can be generated by a recursive algorithm which finds maximum packings in an ultrametric space. Finally, we design a message passing algorithm based on the cavity equations to find dense packings of hard spheres. Known maximum packings are reproduced efficiently in nontrivial ranges of dimensions and number of spheres.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2498001
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo