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.

sympa [at] lists [dot] simons [dot] berkeley [dot] edu (body: (Click here to subscribe to our announcements email list for this program.)


Amir Yehudayoff (Technion Israel Institute of Technology; chair), Russell Impagliazzo (UC San Diego), Toniann 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), Toniann 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), Satish Rao (UC Berkeley), Benjamin Rossman (University of Toronto), Rahul Santhanam (University of Oxford), Alistair Sinclair (UC Berkeley), 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), Richard Zemel (University of Toronto)

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), Rafael Mendes de Oliveira (University of Toronto), 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), Orr Fischer (Tel Aviv University), Noah Fleming (University of Toronto), Venkata Gali (UC San Diego), Ofer Grossman (MIT), Lianna Hambardzumyan (McGill University), Shuichi Hirahara (University of Tokyo), Dhiraj Holden (MIT), Xuangui Huang (Northeastern University), Matthew Katzman (University of Oxford), Saleet Klein (Massachusetts Institute of Technology), Sajin Koroth (University of Haifa), Yaqiao Li (McGill University), Uri Meir (Tel Aviv University), Ian Mertz (University of Toronto), Ivan Mikhailin (UC San Diego), Andrew Morgan (University of Wisconsin-Madison), Kilian Risse (KTH Royal Institute of Technology), Gregory Rosenthal (University of Toronto), Manuel Sabin (UC Berkeley), Morgan Shirley (University of Toronto), Makrand Sinha (University of Washington), Joseph Swernofsky (KTH Royal Institute of Technology), Adrian Trejo Nuñez (University of Texas at Austin)


Aug. 20Aug. 24, 2018


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


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


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


Shubhangi Saraf (Rutgers University; chair), Amir Shpilka (Tel Aviv University), Madhu Sudan (Harvard University)

Those interested in participating in this program should send email to the organizers complexity2018 [at] lists [dot] simons [dot] berkeley [dot] edu (at this address).

Program image by Luisa Lee