Learning ๐– ๐–ข 0 \mathsf{AC}^{0} Under Graphical Models

Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra, Arsen Vasilyan ยท 2026

Read Learning ๐– ๐–ข 0 \mathsf{AC}^{0} Under Graphical Models by Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra, Arsen Vasilyan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-06109.txt.

Description

Chandrasekaran and three colleagues extend a landmark 1993 learning result beyond its original narrow setting. Linial, Mansour, and Nisan proved constant-depth circuits learnable in quasipolynomial time from labeled samples under the uniform distribution, using the low-degree algorithm. The new work handles inputs from any graphical model with polynomial growth and strong spatial mixing, replacing Fourier analysis with new sampling algorithms that transfer low-degree approximation guarantees to these correlated settings. The approach also reaches monotone functions and halfspaces.

Catalog record

CREATORGautam Chandrasekaran, Jason Gaitonde, Ankur Moitra, Arsen Vasilyan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE171395
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.06109

Browse the full library ยท About the Tower of Babel