Part I. (this will be on the Seminar on limits of efficient computation on Marh 15)
I'll survey a variety of connections between non-uniform circuit
lower bounds, non-trivial proof systems, non-trivial learning algorithms, and
variants of natural properties. In particular, I plan to discuss how one can
prove new unconditional lower bounds for standard complexity classes such as
REXP, ZPEXP, BPEXP, and NEXP by designing algorithms with a non-trivial
running time, and to present some open problems.
Part II. I'll focus on a recent application of some of the
complexity-theoretic techniques behind these results. I'll describe in more
detail recent progress on the problem of efficiently generating large
canonical prime numbers, via pseudodeterministic pseudorandomness. If there
is enough time and interest, we will also discuss some non-constructive
aspects of the result, and connections to derandomization.
Based on joint work with Rahul Santhanam.