A. Ramezanpour, R. Zecchina
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 ultra-metric 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 non trivial
ranges of dimensions and number of spheres.
View original:
http://arxiv.org/abs/1201.3863
No comments:
Post a Comment