« search calendars

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

DIMACS Workshop on Meta-Complexity, Barriers, and Derandomization

April 25, 2022 - April 27, 2022


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. 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


Monday, April 25, 2022

9:00 AM - 9:30 AM

Registration and Breakfast

9:30 AM - 10:00 AM

Constructive Separations and Their Consequences

Ryan Williams, Massachusetts Institute of Technology

10:00 AM - 10:30 AM

Large Gaps in Formula Complexity Between Depths

Rahul Ilango, Massachusetts Institute of Technology

10:30 AM - 11:00 AM


11:00 AM - 12:00 PM

Recent Developments in Derandomization I

Lijie Chen, Massachusetts Institute of Technology

12:00 PM - 1:50 PM


1:50 PM - 2:00 PM

DIMACS Welcome Presentation

Tamra Carpenter, DIMACS

2:00 PM - 3:00 PM

Recent Developments in Derandomization II

Roei Tell, DIMACS

3:00 PM - 3:30 PM


3:30 PM - 4:00 PM

Pseudodeterministic Algorithms

Pavan Aduri, Iowa State University

4:00 PM - 4:30 PM

Input-by-Input Derandomization of Arthur-Merlin Protocols

Nicollas Sdroievski, University of Wisconsin, Madison

5:30 PM - 7:30 PM

Workshop Dinner


Tuesday, April 26, 2022

9:30 AM - 10:00 AM

Symmetry of Information and Kolmogorov's approach to P versus NP

Shuichi Hirahara, National Institute of Informatics

10:00 AM - 10:30 AM

Randomness vs. Leakage-resilient Hardness

Yanyi Liu, Cornell University

10:30 AM - 11:00 AM


11:00 AM - 11:30 AM

Hardness of KT Characterizes Parallel Cryptography

Hanlin Ren, University of Oxford

11:30 AM - 12:00 PM

Cryptography from Sublinear Hardness of Time-Bounded Kolmogorov Complexity

Rafael Pass, Cornell University

12:00 PM - 2:00 PM


2:00 PM - 2:30 PM

One-way Functions and a Conditional Variant of MKTP

Dimitrios Myrisiotis, National University of Singapore

2:30 PM - 3:00 PM

Duality in Computational Complexity

Bruno Loff, University of Porto

3:00 PM - 3:30 PM


3:30 PM - 4:00 PM

Probabilistic Kolmogorov Complexity and its Applications

Zhenjian Lu, University of Warwick

4:00 PM - 4:30 PM

Polynomial Identity Testing & the Ideal Proof System

Josh Grochow, University of Colorado

5:30 PM - 7:30 PM

Day Two Dinner


Wednesday, April 27, 2022

9:30 AM - 10:00 AM

Worst-Case to Average-Case Reductions via Additive Combinatorics

Alexander Golovnev, Georgetown University

10:00 AM - 10:30 AM

Extracting Computational Hardness from Learning Algorithms

Igor Carboni Oliveira, University of Warwick

10:30 AM - 11:00 AM


11:00 AM - 11:30 AM

Learning Algorithms Versus Automatability of Frege Systems

Jan Pich, University of Oxford

11:30 AM - 12:00 PM

Efficient Reasoning Can't Distinguish Between Algorithms and Circuits: Proof by Dueling Witnessing Theorems

Marco Carmosino, Simon Fraser University


Presentation at the workshop is by invitation. Attendance at the workshop is open to all who register subject to space limitations and compliance with protocols for COVID-19. As required by Rutgers University, attendees must show proof of vaccination to attend. Additionally, DIMACS requests that masks be worn in the lecture room and other crowded indoor spaces. (Click here for more detailed information on COVID policies.)


If you would like to attend this workshop, please register using the button at the bottom of this page.

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: If you do not have a Rutgers parking permit and you plan to drive to the workshop, there will be free parking available, but you must register your vehicle to park. A link to register for parking will be provided in the confirmation message you receive when you register for the workshop. Once your vehicle has been registered, please park in Lots 74A, 76 & 82 on the days of the event. If you do not register your vehicle, or if you park in unauthorized lots, you may receive a citation. If you are Rutgers-affiliated and already have a Rutgers parking permit, you must park only in lots where you are authorized to park.

Code of Conduct

Registration for this event is closed.