Approximate Capacities of Two-Dimensional Codes by Spatial Mixing
arXiv:1401.4831
Abstract
We apply several state-of-the-art techniques developed in recent advances of counting algorithms and statistical physics to study the spatial mixing property of the two-dimensional codes arising from local hard (independent set) constraints, including: hard-square, hard-hexagon, read/write isolated memory (RWIM), and non-attacking kings (NAK). For these constraints, the strong spatial mixing would imply the existence of polynomial-time approximation scheme (PTAS) for computing the capacity. It was previously known for the hard-square constraint the existence of strong spatial mixing and PTAS. We show the existence of strong spatial mixing for hard-hexagon and RWIM constraints by establishing the strong spatial mixing along self-avoiding walks, and consequently we give PTAS for computing the capacities of these codes. We also show that for the NAK constraint, the strong spatial mixing does not hold along self-avoiding walks.
References in corpus (6)
- Sequential cavity method for computing free energy and surface pressure
- Spatial mixing and approximation algorithms for graphs with bounded connective constant
- The correlation decay (CD) tree and strong spatial mixing in multi-spin systems
- Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets
- Approximate Counting via Correlation Decay in Spin Systems
- Approximate Counting via Correlation Decay on Planar Graphs