skip to main content

Theory of Computing Seminar

Friday, February 5, 2016
12:00pm to 1:00pm
Add to Cal
Annenberg 213
Algorithms from natural lower bounds
Valentine Kabanets, Simon Fraser University,


Based on Hastad's (1986) circuit lower bounds, Linial, Mansour, and Nisan (J ACM, 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 the general connection between natural properties (in the sense of Razborov and Rudich (JCSS, 1997)) and learning algorithms. We show that a natural circuit lower bound against any (sufficiently powerful) circuit class yields a learning algorithm for the same circuit class. Then the known lower bounds against AC^0[p] by Razborov (1987) and Smolensky (1987), shown to be natural by Razborov and Rudich, imply our main result.

Joint work with Marco Carmosino (UCSD), Russell Impagliazzo (UCSD), and Antonina Kolokolova (MUN).  


For more information, please contact Thomas Vidick by email at [email protected].