Fall 2018

Lower Bounds in Computational Complexity

Aug. 15Dec. 14, 2018
The theoretical study of computational intractability is one of the most interesting and challenging endeavors in our quest to understand the capabilities of computational devices.  This study takes many forms, depending on the exact model being investigated and the assumptions being made.  It requires tools and methods from many areas of mathematics, including analysis, geometry, algebra, probability theory, information theory, invariant theory and more.  By now, there are several general principles that guide lower bound proofs, but despite much effort the main questions in most models remain unsolved.

The problem of proving "impossibility" results in mathematics has been studied for ages.  The focus of this program is on proving impossibility results in concrete computational models.  Of course, the most fundamental challenge in this direction is the P versus NP question and its many offshoots, but this challenge seems out of reach at the present time.  Nevertheless, many other basic and interesting questions are still open in models like boolean circuits, branching programs and formulas, algebraic computation, communication complexity, streaming algorithms, data structures, extension complexity of polytopes, and so forth.

The program will explore three distinct classes of models: interactive models, boolean devices and algebraic methods.  Within these models, the program will aim to develop viable research programs for making progress on major open problems in computational lower bounds, identify and investigate connections between different approaches for proving lower bounds in an attempt to unify them, and revisit old approaches and try to revive them using present technology.

Specific challenges that the program will focus on include the following: compression of communication protocols; query complexity in data structures; P versus NC1 and the KRW conjecture; lifting theorems; matrix rigidity; NEXP versus P/poly and uniform lower bounds; limitations of the “constant depth chasm” mechanism; and new approaches towards the VP versus VNP problem.

This program is supported in part by the National Science Foundation, as part of the DIMACS/Simons Institute Collaboration on Lower Bounds in Computational Complexity, and by the Patrick J. McGovern Foundation.



Amir Yehudayoff (Technion Israel Institute of Technology; chair), Russell Impagliazzo (UC San Diego), Toni Pitassi (University of Toronto), Anup Rao (University of Washington), Benjamin Rossman (University of Toronto), Avi Wigderson (Institute for Advanced Study, Princeton), Ryan Williams (Massachusetts Institute of Technology)

Long-Term Participants (including Organizers):

Eric Allender (Rutgers University), Paul Beame (University of Washington), Peter Bürgisser (Technical University of Berlin), Arkadev Chattopadhyay (Tata Institute of Fundamental Research), Faith Ellen (University of Toronto), Yuval Filmus (Technion Israel Institute of Technology), Anna Gál (University of Texas at Austin), Johan Håstad (KTH Royal Institute of Technology), Hamed Hatami (McGill University), Pavel Hrubeš (Academy of Sciences of the Czech Republic), Russell Impagliazzo (UC San Diego), Valentine Kabanets (Simon Fraser University), Richard Karp (UC Berkeley), Pascal Koiran (École Normale Supérieure de Lyon), Antonina Kolokolova (Memorial University of Newfoundland), Kasper Green Larsen (Aarhus University), Nutan Limaye (IIT Bombay), Or Meir (University of Haifa), Jakob Nordström (KTH Royal Institute of Technology), Rotem Oshman (Tel Aviv University), Greta Panova (University of Pennsylvania), Toni Pitassi (University of Toronto), Aaron Potechin (University of Chicago), Pavel Pudlák (Academy of Sciences of the Czech Republic), Prasad Raghavendra (UC Berkeley), Anup Rao (University of Washington), Benjamin Rossman (University of Toronto), Rahul Santhanam (University of Oxford), Srikanth Srinivasan (Indian Institute of Technology Bombay), Nikhil Srivastava (UC Berkeley), Madhu Sudan (Harvard University), Dieter van Melkebeek (University of Wisconsin, Madison), Umesh Vazirani (UC Berkeley), Emanuele Viola (Northeastern University), Martin Wainwright (UC Berkeley), Avi Wigderson (Institute for Advanced Study, Princeton), Ryan Williams (Massachusetts Institute of Technology), Amir Yehudayoff (Technion Israel Institute of Technology; chair)

Research Fellows:

Mark Bun (Princeton University; Google Research Fellow), Igor Carboni Oliveira (University of Oxford), Susanna de Rezende (KTH Royal Institute of Technology; Google Research Fellow), Christian Ikenmeyer (Max Planck Institute for Informatics), Mrinal Kumar (Harvard University), Cody Murray (Massachusetts Institute of Technology), Robert Robere (University of Toronto), Avishay Tal (Stanford University)

Visiting Graduate Students and Postdocs:

Marco Carmosino (UC San Diego), Lijie Chen (Massachusetts Institute of Technology), Raaz Dwivedi (UC Berkeley), Orr Fischer (Tel Aviv University), Noah Fleming (University of Toronto), Avishek Ghosh (UC Berkeley), Ofer Grossman (MIT), Lianna Hambardzumyan (McGill University), Shuichi Hirahara (University of Tokyo), Dhiraj Holden (MIT), Xuangui Huang (Northeastern University), Matthew Katzman (University of Oxford), Sajin Koroth (University of Haifa), Yaqiao Li (McGill University), Uri Meir (Tel Aviv University), Rafael Mendes de Oliveira (University of Toronto), Ian Mertz (University of Toronto), Ivan Mikhailin (UC San Diego), Andrew Morgan (University of Wisconsin-Madison), Sasank Mouli (UC San Diego), Kilian Risse (KTH Royal Institute of Technology), Gregory Rosenthal (University of Toronto), Manuel Sabin (UC Berkeley), Jonathan Shafer (UC Berkeley), Morgan Shirley (University of Toronto), Makrand Sinha (University of Washington), Joseph Swernofsky (KTH Royal Institute of Technology)


Monday, Aug. 20Friday, Aug. 24, 2018


Amir Yehudayoff (Technion Israel Institute of Technology; chair), Anup Rao (University of Washington), Ryan Williams (Massachusetts Institute of Technology)
Monday, Sep. 10Friday, Sep. 14, 2018


Benjamin Rossman (University of Toronto; chair), Rahul Santhanam (University of Oxford), Avi Wigderson (Institute for Advanced Study, Princeton)
Monday, Oct. 15Thursday, Oct. 18, 2018


Kasper Green Larsen (Aarhus University; chair), Mark Braverman (Princeton University), Michael Saks (Rutgers University)
Monday, Dec. 3Friday, Dec. 7, 2018


Shubhangi Saraf (Rutgers University; chair), Amir Shpilka (Tel Aviv University), Madhu Sudan (Harvard University)
Monday, Dec. 9Thursday, Dec. 12, 2019


Amir Yehudayoff (Technion Israel Institute of Technology; chair), Anup Rao (University of Washington), Ryan Williams (Massachusetts Institute of Technology)


Program image by Luisa Lee

Past Internal Program Activities

Monday, December 10th, 1:00 pm3:00 pm
Friday, November 30th, 2:00 pm4:00 pm
Friday, November 30th, 10:30 am12:00 pm
Susanna Rezende and Robert Robere
Thursday, November 29th, 10:30 am12:00 pm
Yuval Filmus
Wednesday, November 28th, 10:30 am12:00 pm
Shai Ben-David
Tuesday, November 27th, 4:00 pm6:00 pm
Monday, November 26th, 1:00 pm3:00 pm
Friday, November 23rd, 2:00 pm4:00 pm
Tuesday, November 20th, 4:00 pm6:00 pm
Monday, November 19th, 1:00 pm3:00 pm
Monday, November 19th, 10:30 am12:00 pm
Jonathan Mosheiff
Friday, November 16th, 2:00 pm4:00 pm
Wednesday, November 14th, 10:30 am12:00 pm
Nutan Limaye
Tuesday, November 13th, 4:00 pm6:00 pm
Monday, November 12th, 1:00 pm3:00 pm
Friday, November 9th, 2:00 pm4:00 pm
Friday, November 9th, 10:30 am12:00 pm
Hamed Hatami (McGill University)
Wednesday, November 7th, 10:30 am12:00 pm
Johan Håstad (KTH Royal Institute of Technology)
Wednesday, October 31st, 11:00 am12:30 pm
Madhu Sudan
Wednesday, October 24th, 10:30 am12:00 pm
Pavel Pudlák
Wednesday, October 10th, 10:30 am12:00 pm
Benjamin Rossman
Wednesday, October 3rd, 10:30 am12:00 pm
Rotem Othman
Wednesday, September 26th, 10:30 am12:00 pm
Mark Bun
Wednesday, September 19th, 10:30 am12:00 pm
Srikanth Srinivasan (IIT Bombay)
Wednesday, September 5th, 10:30 am12:00 pm
Makrand Sinha
Friday, August 31st, 10:30 am12:00 pm
Karthik C. S.