Learning ${\mathsf{AC}}^0$ under Locally Sampleable Graphical Models

Weiming Feng, Xiongxin Yang, Yixiao Yu +1

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,…