Weiming Feng

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

Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang

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 $\mathsf{AC}^0$ under…Read more