Meta-complexity refers to the complexity of computational problems and tasks that are themselves about computations and their complexity. For example, the Minimum Circuit Size Problem (given the truth table of a Boolean function F, compute the minimum circuit size of F) and the problem Kpoly of determining the polynomial-time bounded Kolmogorov complexity of a string are key meta-complexity problems. Meta-complexity provides a unifying framework for a variety of important tasks in several important areas of computer science, including computational complexity, proof complexity, cryptography, and learning theory.
These areas are all intimately linked, but only recently are these links being made explicit and studied more closely. For example, learning can be interpreted as solving search versions of the Minimum Circuit Size Problem and related problems. Basing primitives such as one-way functions and indistinguishability obfuscation on standard complexity assumptions is one of the main objectives in theoretical cryptography. Important recent directions involving meta-complexity within proof complexity, such as lifting and automatability, strengthen analogies and connections between proof complexity and circuit complexity. In addition, independence results such as the natural proofs framework have intuitive interpretations in terms of meta-complexity. These connections have led to several recent breakthroughs, including quasi-polynomial time PAC-learning algorithms for constant-depth circuits with parity gates [Carmosino-Impagliazzo-Kabanets-Kolokolova16], new worst-case to average-case reductions for NP problems [Hirahara18], a new complexity-theoretic characterization of one-way functions [Liu-Pass20], and the NP-hardness of automating Resolution [Atserias-Muller19].
The program will bring together researchers in computational complexity, proof complexity, cryptography, and learning theory for a renewed attack on fundamental problems in these areas by exploiting the tools and techniques of meta-complexity. We also wish to broaden the scope of meta-complexity to areas such as the theory of total function NP search problems, algebraic complexity, and quantum complexity. Among the fundamental problems we plan to tackle are: Is the Minimum Circuit Size Problem NP-hard? Can one-way functions be based on NP-hardness? What are the minimal complexity assumptions for indistinguishability obfuscation? Are DNFs hard to PAC-learn under standard complexity assumptions? Is Resolution weakly automatable?
meta-complexity2023announcements [at] lists.simons.berkeley.edu (Click here to subscribe to our announcements email list for this program.)
Valentine Kabanets (Simon Fraser University), Rafael Pass (Cornell University), Toniann Pitassi (University of Toronto), Rahul Santhanam (University of Oxford)
Long-Term Participants (tentative, including organizers):
Eric Allender (Rutgers University), Benny Applebaum (Tel Aviv University), Albert Atserias (Polytechnic University of Catalonia), Johan Hastad (KTH Royal Institute of Technology), Russell Impagliazzo (UC San Diego), Yuval Ishai (Technion - Israel Institute of Technology), Valentine Kabanets (Simon Fraser University), Antonina Kolokolova (Memorial University of Newfoundland), Nutan Limaye (University of Copenhagen), Huijia (Rachel) Lin (University of Washington), Tal Malkin (Columbia University), Moni Naor (Weizmann Institute of Science), Igor Carboni Oliveira (University of Warwick), Rafael Pass (Cornell University), Jan Pich (University of Oxford), Toniann Pitassi (University of Toronto), Pavel Pudlak (Czech Academy of Sciences), Omer Reingold (Stanford University), Alon Rosen (Reichman University), Mike Saks (Rutgers University), Rahul Santhanam (University of Oxford), Srikanth Srinivasan (Aarhus University), Iddo Tzameret (Imperial College London), Salil Vadhan (Harvard University), Vinod Vaikuntanathan (MIT), Ryan Williams (MIT)