Program
s
Spring 2023

Meta-Complexity

Jan. 10May 12, 2023

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?

Click here to subscribe to our news and events to learn more about this and other events.

Organizers:

Valentine Kabanets (Simon Fraser University), Rafael Pass (Cornell University), Toni Pitassi (University of Toronto), Rahul Santhanam (University of Oxford)

Long-Term Participants (including Organizers):

Pavan Aduri (Iowa State University), Eric Allender (Rutgers University), Amos Beimel (Ben Gurion University), María Luisa Bonet Carbonell (Universitat Politècnica de Catalunya), Igor Carboni Oliveira (University of Warwick), Susanna de Rezende (Lund University), Shuichi Hirahara (National Institute of Informatics, Tokyo), Russell Impagliazzo (UC San Diego), Yuval Ishai (Technion Israel Institute of Technology), Brendan Juba (Washington University in St. Louis), Valentine Kabanets (Simon Fraser University), Yael Kalai (MIT), Antonina Kolokolova (Memorial University of Newfoundland), Michal Koucky (Charles University), Nutan Limaye (IT University of Copenhagen), Tal Malkin (Columbia University), Rafael Pass (Cornell University), Ján Pich (Oxford University), Toni Pitassi (University of Toronto), Pavel Pudlák (Czech Academy of Sciences), Daniel Reichman (WPI), Omer Reingold (Stanford University), Michael Saks (Rutgers University), Rahul Santhanam (University of Oxford), Srikanth Srinivasan (Aarhus University), Iddo Tzameret (Imperial College London), Vinod Vaikuntanathan (MIT), Ryan Williams (MIT)

Research Fellows:

Marshall Ball (New York University), Marco Carmosino (UC San Diego), Lijie Chen (UC Berkeley), Alex Lombardi (MIT), Zhenjian Lu (University of Warwick), Robert Robere (McGill University), Roei Tell (Weizmann Institute of Science)

Visiting Graduate Students and Postdocs:

Noel Arteche (Lund University), Gaia Carenini (University of Copenhagen & Lund University), Sayak Chakrabarti (Columbia University), Miranda Christ (Columbia University), Ben Davis (Mcgill University), John Dellas (McGill University), Ted Edward (MIT), Ludmila Glinskih (Boston University), Halley Goldberg (Simon Fraser University), Eli Goldin (New York University), Matthew Gray (University of Oxford), Svyatoslav Griaznov (Imperial College London), Stefan Grosser (McGill University), Tuomas Hakoniemi (Imperial College London & MRC London Institute of Medical Sciences), Peter Hall (New York University), Jizhou Huang (Washington University in St. Louis), Rahul Ilango (MIT), Ari Karchmer (Boston University), Oliver Korten (Columbia University), Sihyun Lee (New York University), Yanyi Liu (Cornell University), Ian Mertz (University of Toronto), Daniel Mitropolsky (Columbia University), Shivam Nadimpalli (Columbia University), Mikito Nanashima (Tokyo Institute of Technology), Bruno Pasqualotto Cavalar (University of Warwick), William Pires (McGill University), Hanlin Ren (University of Oxford), Greg Rosenthal (University of Toronto), Harsha Srimath Tirumala (Rutgers University), Neekon Vafa (MIT), Gal Yehuda (Technion)

Workshops

Tuesday, Jan. 17Friday, Jan. 20, 2023

Organizers:

Toni Pitassi (University of Toronto; co-chair), Rahul Santhanam (University of Oxford; co-chair), Valentine Kabanets (Simon Fraser University), Rafael Pass (Cornell University)
Monday, Feb. 13Friday, Feb. 17, 2023

Organizers:

Valentine Kabanets (Simon Fraser University; chair), Igor Carboni Oliveira (University of Warwick), Russell Impagliazzo (UC San Diego)
Monday, Mar. 20Friday, Mar. 24, 2023

Organizers:

Iddo Tzameret (Imperial College London; chair), Toni Pitassi (University of Toronto), Rahul Santhanam (University of Oxford)
Monday, May 1Friday, May 5, 2023

Organizers:

Rafael Pass (Cornell University; chair), Yuval Ishai (Technion Israel Institute of Technology), Yael Kalai (MIT)

Internal Program Activities

Friday, January 13th, 3:00 pm – 5:00 pm