Distributional PAC-Learning from Nisan's Natural Proofs

Ari Karchmer

Carmosino et al. (2016) demonstrated that natural proofs of circuit lower bounds for $\Lambda$ imply efficient algorithms for learning $\Lambda$-circuits, but only over \textit{the uniform dis…