About
Boolean devices - circuits, branching programs, formulas, etc. - are natural and interesting objects to study in terms of computational complexity. Proving lower bounds in these models is a fundamental challenge. Although simple counting arguments show that most Boolean functions have exponential complexity, we only know fairly weak lower bounds for “explicit" functions in NP or even in exponential time.
In recent years there has been significant progress in proving stronger lower bounds, although mainly in restricted settings such as the monotone and low-depth regimes. This progress has involved deeper understanding of classical techniques such as random restrictions and the polynomial method, developments in communication complexity and its applications to circuit lower bounds, and new connections with circuit analysis tasks such as satisfiability, learning and derandomization. Do these techniques bring us closer, e.g., to proving super polynomial formula-size lower bounds?
This workshop aims to gather together researchers interested in these developments, with a view towards pushing known techniques further as well as better understanding barriers to strong circuit lower bounds.
Chairs/Organizers
Invited Participants
Eric Allender (Rutgers University), Kazuyuki Amano (Gunma University), Paul Beame (University of Washington), Mark Bun (Princeton University), Sam Buss (UC San Diego), Igor Carboni Oliveira (University of Oxford), Marco Carmosino (UC San Diego), Arkadev Chattopadhyay (Tata Institute of Fundamental Research), Eshan Chattopadhyay (Cornell University), Lijie Chen (MIT), Aloni Cohen (Massachusetts Institute of Technology), Susanna de Rezende (KTH Royal Institute of Technology), Faith Ellen (University of Toronto), Yuval Filmus (Technion - Israel Institute of Technology), Noah Fleming (University of Toronto), Anna Gál (University of Texas at Austin), Venkata Gali (UC San Diego), Jiawei Gao (UC San Diego), Sasha Golovnev (Columbia University), Mika Göös (University of Toronto), Parikshit Gopalan (VMware Research), Lianna Hambardzumyan (McGill University), Kristoffer Hansen (Aarhus University), Hamed Hatami (McGill University), Pooya Hatami (University of Chicago), Shuichi Hirahara (The University of Tokyo), Edward Hirsch (Steklov Institute of Mathematics at St.Petersburg), Dhiraj Holden (MIT), Kaave Hosseini (UC San Diego), Xuangui Huang (Northeastern University), Christian Ikenmeyer (Max-Planck-Institut für Informatik), Russell Impagliazzo (UC San Diego), Valentine Kabanets (Simon Fraser University), Dick Karp (UC Berkeley), Matthew Katzman (University of Oxford), Antonina Kolokolova (Memorial University of Newfoundland), Sajin Koroth (University of Haifa), Michal Koucky (Charles University), Sasha Kulikov (St. Petersburg Department of Steklov Institute of Mathematics), Mrinal Kumar (Harvard University), Kasper Larsen (Aarhus University), Meena Mahajan (Institute of Mathematical Sciences), Jenish Mehta (Caltech), Or Meir (University of Haifa), Uri Meir (Tel Aviv University), Rafael Mendes de Oliveira (University of Toronto), Ian Mertz (University of Toronto), Ivan Mikhailin (UC San Diego), Dor Minzer (Tel Aviv University), Andrew Morgan (University of Wisconsin, Madison), Cody Murray (MIT), Jakob Nordström (KTH Royal Institute of Technology), Rotem Oshman (Tel Aviv University), Toni Pitassi (University of Toronto), Aaron Potechin (University of Chicago), Robert Robere (University of Toronto), Greg Rosenthal (University of Toronto), Rocco Servedio (Columbia University), Sasha Sherstov (UCLA), Morgan Shirley (University of Toronto), Dmitry Sokolov (KTH Royal Institute of Technology), Srikanth Srinivasan (Indian Institute of Technology Bombay), Avishay Tal (Stanford University), Suguru Tamaki (Kyoto University), Li-Yang Tan (Stanford University), Roei Tell (Weizmann Institute of Science), Dieter Van Melkebeek (U Wisconsin-Madison), Emanuele Viola (Northeastern University), Ryan Williams (MIT), Amir Yehudayoff (Technion Israel Institute of Technology)