# Learning mathsfAC0 under Locally Sampleable Graphical Models

arXiv: https://arxiv.org/abs/2607.08303 · HTML: https://mlsanity.com/paper/2607.08303/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 42 references that are in the map.
- First posted on arXiv 9 Jul 2026.

## Builds on (most cited first, 19 of 19)

- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications](https://mlsanity.com/paper/1705.11107/) (2017)
- [Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models](https://mlsanity.com/paper/1810.11905/) (2018)
- [ID3 Learns Juntas for Smoothed Product Distributions](https://mlsanity.com/paper/1906.08654/) (2019)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Learning the Sherrington-Kirkpatrick Model Even at Low Temperature](https://mlsanity.com/paper/2411.11174/) (2024)
- [Learning Juntas under Markov Random Fields](https://mlsanity.com/paper/2506.00764/) (2025)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [MCMC Learning](https://mlsanity.com/paper/1307.3617/) (2013)
- [Perfect Sampling in Infinite Spin Systems via Strong Spatial Mixing](https://mlsanity.com/paper/2106.15992/) (2021)
- [Perfect Sampling for Hard Spheres from Strong Spatial Mixing](https://mlsanity.com/paper/2305.02450/) (2023)
- [Approximate Counting for Spin Systems in Sub-Quadratic Time](https://mlsanity.com/paper/2306.14867/) (2023)
- [Random local access for sampling k-SAT solutions](https://mlsanity.com/paper/2409.03951/) (2024)
- [Sink-free orientations: a local sampler with applications](https://mlsanity.com/paper/2502.05877/) (2025)
- [Local Gibbs sampling beyond local uniformity](https://mlsanity.com/paper/2502.10795/) (2025)
- [Subquadratic Counting via Perfect Marginal Sampling](https://mlsanity.com/paper/2604.02235/) (2026)

## Built on by (most cited first, 1 of 1)

- [Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm](https://mlsanity.com/paper/2609.15268/) (2026)

## Abstract (arXiv)

The problem of learning constant-depth circuits holds profound implications for computational learning theory. In a seminal result, by introducing the low-degree algorithm, Linial, Mansour, and Nisan (J. ACM 1993) presented a quasipolynomial-time learner for mathsfAC0 under the uniform distribution. However, obtaining comparable learning guarantees for broader classes of correlated distributions has remained a longstanding challenge. Recently, Chandrasekaran, Gaitonde, Moitra, and Vasilyan (arXiv 2026) extended these guarantees to Gibbs distributions on bounded-degree graphical models with both strong spatial mixing and polynomial growth. In this paper, we give a quasipolynomial-time learner for mathsfAC0 under graphical models that admit efficient local samplers, circumventing the polynomial-growth requirement in prior work. The key ingredient is a new low-degree approximation for Gibbs distributions, established by simulating and suitably truncating the classical Glauber dynamics. As applications, this framework yields learners for two-spin systems, including the hard-core model and Ising model, on arbitrary bounded-degree graphs, in regimes approaching their respective sampling thresholds.