Abstract

Explicit constructions of pseudorandom objects (e.g., pseudorandom generators, expander graphs, or boolean functions of large circuit complexity) often come with very constructive proofs of existence. For example,
 
(1) the Nisan-Wigderson (NW) generator based on an assumed ``hard'' function f (of large circuit complexity) has the constructive analysis: There is an efficient uniform reduction (with oracle access to f) taking an algorithm ``breaking'' the generator into a small circuit for f;
 
(2) the Natural Proofs framework of Razborov and Rudich argues that most circuit lower bound proofs come with an efficiently testable property  that distinguishes ``easy'' functions (with small circuit complexity) from random functions;
 
(3) the analysis of the iterative Zig-Zag construction of expanders due to Reingold, Vadhan, and Wigderson contains an efficient algorithm taking a non-expanding set of vertices in the graph at any given stage i into a non-expanding set of vertices in the graph at the previous stage (i-1). 
 
I'll talk about several recent applications of such constructive proofs: 
 
*  Properties (1) + (2)  yield an efficient (agnostic) learning query algorithm for every sufficiently strong circuit class that has a natural proof of circuit lower bounds.  As an application, the class AC^0[p], for any prime p, is (agnostically) learnable in quasi-polynomial time. (Previously, only the case of AC^0 was known by the results of Linial, Mansour, and Nisan.)  [joint with Carmosino, Impagliazzo, and Kolokolova.] 
 
* The analysis of the zig-zag construction in (3) can be made even more constructive: it is formalizable in the theory VNC^1 of NC^1-reasoning. This implies (using the previous work by Jerabek) that  monotone LK (MLK) proof system polynomially simulates LK proof system on monotone sequents, strengthening the quasi-polynomial simulation result by Atserias, Galesi, and Pudlak.  [joint with S. Buss, Kolokolova, and Koucky.]

 

Attachment

Video Recording