The workshop is over. Thank you to all the speakers and attendees!
Video: The workshop was recorded on the official ACM youtube channel.
Time and Date: 12:00 CDT to 15:00 CDT (UTC -5), Monday, June 22
Topic: The Minimum Circuit Size Problem (MCSP) asks: given the complete truth table of a Boolean function f, and an integer s, does f have a circuit of size at most s? MCSP is a natural and well-studied problem in NP, but we do not yet know if it is NP-hard. Instead, we have formal evidence that resolving the complexity of MCSP is hard.
Despite (and often because of) this, exciting results have recently emerged that leverage connections between MCSP and fundamental questions in theoretical computer science (including P vs NP, circuit lower bounds, derandomization, learning, and cryptography). These new connections deepen both our structural understanding of and concrete bounds on MCSP and related “meta-computational” problems.
Agenda:
Schedule and Speaker List:
Organizers: Josh Alman, Marco Carmosino, Ryan Williams
While MCSP is easily seen to be in NP (guess a circuit of size s and then check if it computes f), it is still unknown if MCSP is NP-complete. In fact, Leonid Levin (co-discoverer of NP-completeness) delayed his NP-completeness paper in the 1970s because he tried to prove that MCSP is NP-complete, but could not. The question of whether MCSP is NP-complete remains open today.
MCSP is a meta-computational problem that has applications to a number of areas of theoretical computer science: circuit complexity, cryptography, computational learning, proof complexity, and more. Since around 2015, there has been an increased interest in MCSP, with many research papers coming out in the past couple of years.
In this talk, I will present some recent results on the circuit complexity of MCSP against several restricted circuit models, which essentially match the known state-of-the-art circuit lower bounds known today for explicit boolean functions. In particular, I will show that MCSP requires exponential-size circuits of constant depth, with AND, OR, NOT, and PARITY gates (of unbounded fanin), i.e., the circuit class AC0[2]. I will also talk about almost-cubic lower bounds against boolean formulas with AND, OR, and NOT gates (de Morgan formulas).
(Based on the joint works with A. Golovnev, R. Ilango, R. Impagliazzo, A. Kolokolova and A. Tal, as well as M. Cheraghchi, Z. Lu, and D. Myrisiotis.)
A small circuit is a short description of a (much larger) truth table for a Boolean function. Thus it is clear that there should be some connections between the study of MCSP and the study of Kolmogorov complexity (which is all about short descriptions of objects). But different theorems of interest to the MCSP community deal with different variants of Kolmogorov complexity. This talk will introduce some of the different variants that are being studied, and explain why.
Hardness magnification shows that minor extensions of some known circuit lower bounds (e.g. by a layer of parities) would provide a solution to longstanding questions in complexity theory. This talk will explain this phenomenon in more detail, discuss the role of MCSP and its variants, and highlight some recent results and directions.
The Razborov-Rudich paper on “Natural Proofs” is one of the most influential papers in the history of complexity theory. Implicit in the paper are connections between the complexity of MCSP and fundamental concepts in cryptography and proof complexity. Using the “Natural Proofs” paper as a starting point, I will briefly survey work on these connections, and highlight some key open problems.