Deterministic Approximation via Spatial Correlation Decay

60 concepts41 papers1 proposal

Many fundamental problems in computer science and statistical physics—such as counting the number of valid graph colorings, independent sets, or computing marginal probabilities in a graphical model—are globally coupled. In the worst case, changing a single variable's state can ripple across an entire network, making exact computation #P-hard or NP-hard.

However, in many practical systems, this ripple effect dies out. This phenomenon is known as spatial correlation decay or strong spatial mixing. When a system exhibits correlation decay, the mutual influence between two distant variables diminishes exponentially with the distance between them. This simple property provides a powerful recipe for bypassing global complexity, enabling researchers to design efficient, deterministic local algorithms for massive systems.

The Core Intuition: Locality in Global Systems

To understand why correlation decay works, imagine a massive network—such as a social network, a grid of atoms in a magnetic model, or a constraint satisfaction problem like random $k$-SAT. If you want to find the marginal probability that a specific root node takes a certain value, you might worry that a choice made thousands of steps away will dictate the outcome.

As Bandyopadhyay et al. demonstrate in the context of Gibbs measures on infinite trees, correlation decay guarantees that the influence of distant boundary conditions on a root node vanishes as the distance increases. This means that the local statistical properties of a large graph are effectively insulated from distant structural variations. For instance, Montanari et al. leveraged this insight to develop a deterministic, polynomial-time algorithm to approximate the number of satisfying assignments for random $k$-SAT formulae, showing that local message-passing accurately captures global properties when long-range dependencies vanish.

From Tree Recurrences to Polynomial-Time Algorithms

The primary algorithmic benefit of correlation decay is that it turns intractable global counting problems into a simple, truncated local search.

To compute a marginal probability or a partition function contribution at a specific node, we can "unroll" the local neighborhood of the graph into a computation tree. Because a tree has no loops, the marginal probability of the root can be computed exactly via a deterministic recurrence relation from its children. Normally, to get a perfectly exact answer, we would have to unroll this tree all the way to the boundaries of the graph, which could be exponentially large.

       [ Root ]
        /    \
     [A]      [B]
     / \      / \
   [.] [.]  [.] [.]   <-- Truncate here at depth d = O(log(1/ε))
   / \ / \  / \ / \
  [  Ignored Subtree  ]  <-- Exponentially small impact on Root

If a system exhibits exponential correlation decay, the error introduced by completely ignoring the graph beyond a certain depth $d$ shrinks exponentially:

$$\text{Error} \le C \cdot \alpha^d$$

where $\alpha < 1$ is a constant dictating the rate of decay. To achieve an arbitrary error tolerance of $\epsilon$, we only need to unroll the computation tree to a depth of:

$$d = O\left(\log \frac{1}{\epsilon}\right)$$

For a graph with a bounded maximum degree $\Delta$, the total number of nodes in a tree of depth $d$ is at most $\Delta^d$. Substituting our required depth, the size of our local computation tree becomes:

$$\Delta^{O(\log(1/\epsilon))} = \left(\frac{1}{\epsilon}\right)^{O(\log \Delta)}$$

Crucially, this size is entirely independent of the total number of nodes $n$ in the global graph. It depends only on the degree bound and the desired precision. This mathematical guarantee allows for the construction of a Fully Polynomial-Time Approximation Scheme (FPTAS)—a deterministic algorithm providing arbitrary precision in polynomial time. Liu et al. utilized this exact mechanism to design the first deterministic FPTAS for counting edge covers across arbitrary graphs.

Expanding the Algorithmic Frontier of Counting

The correlation decay framework has successfully bypassed traditional computational barriers across a wide variety of combinatorial problems:

  • Planar and Minor-Free Graphs: Zhang et al. established that strong spatial mixing serves as a sufficient condition to create deterministic FPTASs for counting colorings, matchings, and Potts model configurations on planar and apex-minor-free graphs.
  • Asymmetric Constraints: In bipartite counting problems (#BIS), traditional algorithms often require strict degree bounds on both sides of the graph. However, Liu et al. designed an FPTAS requiring a degree bound on only one side. They discovered that high-degree vertices on the unconstrained side act as powerful local constraints that actually accelerate the decay of correlations between distant nodes.
  • Holographic Reductions and Hypergraphs: The technique is not limited to simple graphs. Lu et al. combined correlation decay with holographic reductions to solve weighted Fibonacci gates, while Lu et al. extended the approach to multi-particle interactions on hypergraphs for hardcore and Ising models.

Localized Inference and Rapidly Mixing Samplers

Beyond counting, correlation decay explains why local, heuristic algorithms perform remarkably well on massive, global tasks. In probabilistic graphical models, exact inference is generally NP-hard. However, Chen et al. showed that under correlation decay, marginal distributions can be accurately estimated by restricting computation to a small neighborhood around a query node, with the approximation error decreasing exponentially with the neighborhood's radius. Similarly, Geier et al. demonstrated that the impact of conditioning a variable is primarily concentrated within its immediate topological neighborhood, justifying localized variants of Belief Propagation.

This principle also governs the dynamics of randomized sampling algorithms like Gibbs sampling (Glauber dynamics). When a system exhibits spatial decay of correlations, local updates do not trigger long-range cascades that stall convergence. Sly proved that Gibbs sampling can efficiently sample $q$-colorings on Erdős–Rényi random graphs in polynomial time, breaking the traditional dependence on worst-case maximum degrees. Mossel et al. established a similar rapid mixing result for the Ising model on average-sparse graphs.

In the engineering of error-correcting codes, Kudekar et al. and Macris et al. used correlation decay to prove that for Low-Density Parity-Check (LDPC) codes operating under low- or high-noise conditions, practical local decoders (like Belief Propagation) asymptotically match the performance of optimal, computationally intractable global decoders.

Graph Algorithms and Online Contention

Correlation decay has also emerged as a powerful tool for analyzing dynamic graph algorithms, online matching, and constraint satisfaction:

  • Local Resampling: Iliopoulos et al. showed that violated constraints in large multigraphs can be fixed via local search and resampling without disrupting the global state, provided the underlying graph exhibits correlation decay.
  • Online and Stochastic Matching: In online settings where edges arrive adversarially or stochastically, Kulkarni et al. designed online edge coloring algorithms by using tree recurrences and correlation decay to tightly bound the errors introduced by adversarial choices. Similarly, Ma et al. used a correlation decay argument to approximate the local neighborhood of an edge as an independent tree structure in the vanishing probability regime. To prove that complex global matchings can be treated as independent local events, Azarmehr et al. utilized local computation algorithms to bound the spatial spread of dependencies.

Structure Learning and Computational Boundaries

If correlations decay rapidly, can we learn the structure of an unknown network from data? Anandkumar et al. demonstrated that under correlation decay, the local statistics of a loopy graph are indistinguishable from a tree, enabling efficient structure learning of latent graphical models. For relational data where samples are inherently connected, Ahsan et al. showed that non-parametric statistical tests remain consistent because the dependencies remain localized rather than global. Even when data is hidden or censored, Moitra et al. showed that correlation decay allows algorithms to learn how to generate new samples without needing to reconstruct the entire global network.

Conversely, the absence of correlation decay marks a fundamental computational boundary—a phase transition. Mossel et al. proved that influence maximization in Ising models is solvable in linear time when correlations decay quickly, but becomes NP-hard as soon as the system crosses into a low-temperature regime where long-range correlations persist.

For property testing and sublinear algorithms, correlation decay acts as an information barrier. Yoshida showed that when correlations decay exponentially, local views of a constraint satisfaction problem appear tree-like and hide global satisfiability, establishing strict lower bounds on query complexity. Similarly, Behnezhad et al. utilized correlation decay to prove lower bounds on the query complexity of approximate maximum matching in sublinear time, demonstrating that global properties become inaccessible through local structural probes when long-range information is lost.

Unifying Algorithmic Paradigms

Finally, correlation decay unifies seemingly disparate mathematical techniques. Gamarnik established a profound theoretical link showing that the success of Barvinok's polynomial interpolation method—a technique based on proving the absence of complex zeros in a partition function—inherently implies the presence of strong spatial mixing. Whether counting solutions, running local message passing, or proving complexity lower bounds, the underlying engine remains the same: when the tyranny of distance holds, global complexity dissolves into local tractability.

Key Foundational Work

Counting good truth assignments of random k-SAT formulae (2006) — contributed 2 concept elements to this direction.
Counting without sampling: new algorithms for enumeration problems using statistical physics (2006) — contributed 2 concept elements to this direction.
Correlation decay and deterministic FPTAS for counting list-colorings of a graph (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_correlation_decay_2bb1924c,
  title = {correlation decay},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/correlation-decay/rdr_2bb1924cdc634b4da4aaba0decf69dae},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_correlation_decay_2bb1924c_v1,
  title = {correlation decay},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/correlation-decay/rdr_2bb1924cdc634b4da4aaba0decf69dae/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake