Workshop Details

Update on scheduling: This workshop was originally scheduled for April 27-29, 2020 but was postponed because of COVID-19. Though we had hoped to hold it in the summer/fall of 2021, lingering concerns led to the decision to reschedule for April 25-27, 2022.

One of the more encouraging trends in the recent history of computational complexity theory is the fact that some of the most significant progress on circuit lower bounds has arisen, in part, through the study of what had originally been presented as "barriers" to obtaining lower bounds (relativization, algebrization, and the "natural proofs" barrier).

To highlight one example, study of the Natural Proofs framework has focused attention on the task of taking as input the truth table of a Boolean function f and determining certain properties of f.  One such problem is the Minimum Circuit Size Problem (MCSP): the task of computing the size of the smallest circuit that computes f.  If f does have a small circuit, then the circuit is essentially a short description (or a “compressed representation”) of f, and hence there are important connections between this topic and time-bounded Kolmogorov complexity. Recent investigations of these notions have pointed to instances in which seemingly minor improvements to currently-known lower bounds would enable intractability arguments to be "magnified", thereby leading to important separations of complexity classes.  Related work shows how to capitalize on seemingly slight algorithmic advances to obtain circuit lower bounds.

These investigations are instances of what we informally term “meta-complexity”. Meta-complexity refers to the computational complexity of problems whose instance themselves encode algorithms or computations. Some of the fundamental questions in theoretical computer science are questions about meta-complexity, including: Can one approximate in less than exponential time the probability that a circuit accepts? Do pseudo-random generators exist? Is efficient learning of concepts feasible? Are complexity lower bounds provable in standard proof systems? These questions connect complexity theory to a wide range of other areas, including algorithm design, derandomization, learning, cryptography, and logic.

View Video Playlist