# Learning mathsfAC0 Under Graphical Models

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 99 references that are in the map.
- First posted on arXiv 7 Apr 2026.

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

- [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025)
- [The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning](https://mlsanity.com/paper/2010.11925/) (2020)
- [Learning Juntas under Markov Random Fields](https://mlsanity.com/paper/2506.00764/) (2025)
- [Better Models and Algorithms for Learning Ising Models from Dynamics](https://mlsanity.com/paper/2507.15173/) (2025)
- [Smoothed Agnostic Learning of Halfspaces over the Hypercube](https://mlsanity.com/paper/2511.17782/) (2025)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)

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

- [Learning with Simulators: No Regret in a Computationally Bounded World](https://mlsanity.com/paper/2606.13576/) (2026)

## Abstract (arXiv)

In a landmark result, Linial, Mansour and Nisan (J. ACM 1993) gave a quasipolynomial-time algorithm for learning constant-depth circuits given labeled i.i.d. samples under the uniform distribution. Their work has had a deep and lasting legacy in computational learning theory, in particular introducing the textitlow-degree algorithm. However, an important critique of many results and techniques in the area is the reliance on product structure, which is unlikely to hold in realistic settings. Obtaining similar learning guarantees for more natural correlated distributions has been a longstanding challenge in the field. In particular, we give quasipolynomial-time algorithms for learning mathsfAC0 substantially beyond the product setting, when the inputs come from any graphical model with polynomial growth that exhibits strong spatial mixing. The main technical challenge is in giving a workaround to Fourier analysis, which we do by showing how new sampling algorithms allow us to transfer statements about low-degree polynomial approximation under the uniform setting to graphical models. Our approach is general enough to extend to other well-studied function classes, like monotone functions and halfspaces.