Talks

Spring 2017

# The Uncanny Usefulness of Constructive Proofs of Pseudorandomness

Monday, March 6th, 2017 9:30 am – 10:00 am

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 | Size |
---|---|

The Uncanny Usefulness of Constructive Proofs of Pseudorandomness | 4.43 MB |