« search calendars

« DIMACS Workshop on Meta-Complexity, Barriers, and Derandomization

DIMACS Workshop on Meta-Complexity, Barriers, and Derandomization

August 09, 2021 - August 13, 2021


Rutgers University Inn and Conference Center

Conference Room A


Eric Allender, Rutgers University

Antonina Kolokolova, Memorial University of Newfoundland

Periklis Papakonstantinou, Rutgers University

Rahul Santhanam, University of Oxford

Update on scheduling: This workshop was originally scheduled for April 27-29, 2020 but was postponed because of COVID-19. The new dates for the workshop will be during the week of August 9-13, 2021. The workshop will be for three days during this period, with precise dates selected early in 2021.

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.


Presentation at the workshop is by invitation. Attendance at the workshop is open to all interested participants (subject to space limitations). Please register if you would like to attend this workshop.

Lodging: The workshop is being held at the Rutgers Inn & Conference Center, which has lodging available on site. Please be aware that the Inn is small, so you will need to book early to stay there.

Parking: There is free parking at the Rutgers Inn and Conference Center for workshop attendees.

Registration is required but not yet open.