2026-07-23T19:43:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5855 2024-03-06T10:37:09Z ddc:004 open_access

Learning Algorithms from Natural Proofs Carmosino, Marco L. Impagliazzo, Russell Kabanets, Valentine Kolokolova, Antonina natural proofs circuit complexity lower bounds learning compression Based on Hastad's (1986) circuit lower bounds, Linial, Mansour, and Nisan (1993) gave a quasipolytime learning algorithm for AC^0 (constant-depth circuits with AND, OR, and NOT gates), in the PAC model over the uniform distribution. It was an open question to get a learning algorithm (of any kind) for the class of AC^0[p] circuits (constant-depth, with AND, OR, NOT, and MOD_p gates for a prime p). Our main result is a quasipolytime learning algorithm for AC^0[p] in the PAC model over the uniform distribution with membership queries. This algorithm is an application of a general connection we show to hold between natural proofs (in the sense of Razborov and Rudich (1997)) and learning algorithms. We argue that a natural proof of a circuit lower bound against any (sufficiently powerful) circuit class yields a learning algorithm for the same circuit class. As the lower bounds against AC^0[p] by Razborov (1987) and Smolensky (1987) are natural, we obtain our learning algorithm for AC^0[p]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marco L. Carmosino and Russell Impagliazzo and Valentine Kabanets and Antonina Kolokolova 2016 Is Part Of LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2016.10 urn:nbn:de:0030-drops-58557 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.10 eng https://creativecommons.org/licenses/by/3.0/legalcode