Approximate capacities of two-dimensional codes by spatial mixing

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. The existence of strong spatial mixing and a PTAS were previously known for the hard-square constraint. We show the existence of strong spatial mixing for hard-hexagon and RWIM constraints, and consequently we give PTAS for computing the capacities of these codes. We also show evidence that the strong spatial mixing may not hold for the NAK constraint.