« DIMACS Workshop on Meta-Complexity, Barriers, and Derandomization
DIMACS Workshop on Meta-Complexity, Barriers, and Derandomization
April 25, 2022 - April 27, 2022
Location:
Rutgers University Inn and Conference Center
Conference Room A
Organizer(s):
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.
Monday, April 25, 2022
Registration and Breakfast
Constructive Separations and Their Consequences
Ryan Williams, Massachusetts Institute of Technology
Large Gaps in Formula Complexity Between Depths
Rahul Ilango, Massachusetts Institute of Technology
Break
Recent Developments in Derandomization I
Lijie Chen, Massachusetts Institute of Technology
Lunch
DIMACS Welcome Presentation
Tamra Carpenter, DIMACS
Recent Developments in Derandomization II
Roei Tell, DIMACS
Break
Pseudodeterministic Algorithms
Pavan Aduri, Iowa State University
Input-by-Input Derandomization of Arthur-Merlin Protocols
Nicollas Sdroievski, University of Wisconsin, Madison
Workshop Dinner
Tuesday, April 26, 2022
Symmetry of Information and Kolmogorov's approach to P versus NP
Shuichi Hirahara, National Institute of Informatics
Randomness vs. Leakage-resilient Hardness
Yanyi Liu, Cornell University
Break
Hardness of KT Characterizes Parallel Cryptography
Hanlin Ren, University of Oxford
Cryptography from Sublinear Hardness of Time-Bounded Kolmogorov Complexity
Rafael Pass, Cornell University
Lunch
One-way Functions and a Conditional Variant of MKTP
Dimitrios Myrisiotis, National University of Singapore
Duality in Computational Complexity
Bruno Loff, University of Porto
Break
Probabilistic Kolmogorov Complexity and its Applications
Zhenjian Lu, University of Warwick
Polynomial Identity Testing & the Ideal Proof System
Josh Grochow, University of Colorado
Day Two Dinner
Wednesday, April 27, 2022
Worst-Case to Average-Case Reductions via Additive Combinatorics
Alexander Golovnev, Georgetown University
Extracting Computational Hardness from Learning Algorithms
Igor Carboni Oliveira, University of Warwick
Break
Learning Algorithms Versus Automatability of Frege Systems
Jan Pich, University of Oxford
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.
Presented in association with the Special Focus on Lower Bounds in Computational Complexity.