Department of Computer, Control and Management Engineering

Abstract

For decades, fundamental questions in complexity theory have remained wide open. A classic counting argument by Shannon shows that most Boolean functions on n bits require circuits of size 2^n/n, yet we lack even superlinear circuit size lower bounds for any explicit function in NP. This raises two natural questions: (i) can we make these counting arguments constructive, and (ii) why have we struggled so much to find an explicit hard function?


In this talk, we rigorously examine two algorithmic and metamathematical notions of constructivity in complexity theory, and how they are related to circuit lower bounds and barrier results. We will demonstrate that


(i) New constructive proofs of known nonconstructive lower bounds imply strong, breakthrough lower bounds.

(ii) Some nonconstructive proofs of lower bounds cannot be made constructive.


We show how these ideas can be used to make unconditional progress on an old question in proof complexity and bounded arithmetic.