Learning algorithms from natural proofs

摘要: Based on Hastad's (1986) circuit lower bounds, Linial, Mansour, and Nisan (1993) gave a quasipolytime learning algorithm for AC0 (constant-depth circuits with AND, OR, NOT gates), in the PAC model over uniform distribution. It was an open question to get (of any kind) class of AC0[p] (constant-depth, NOT, MODp gates prime p). Our main result is distribution membership queries. This application general connection we show hold between natural proofs (in sense Razborov Rudich (1997)) algorithms. We argue that proof bound against (sufficiently powerful) yields same class. As bounds by (1987) Smolensky are natural, obtain our AC0[p].