Fall 2018

Boolean Devices

Sep. 10Sep. 14, 2018

Add to Calendar


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

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.

Enquiries may be sent to the organizers workshop-complexity2018-1 [at] lists [dot] simons [dot] berkeley [dot] edu (at this address).

Registration is now CLOSED.

Invited Participants: 

Kazuyuki Amano (Gunma University), Andrej Bogdanov (The Chinese University of Hong Kong), 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), Susanna de Rezende (KTH Royal Institute of Technology), Yuval Filmus (Technion - Israel Institute of Technology), Jiawei Gao (UC San Diego), Sasha Golovnev (Columbia University), Mika Göös (University of Toronto), Parikshit Gopalan (VMware Research), Kristoffer Hansen (Aarhus University), Pooya Hatami (University of Chicago), Shuichi Hirahara (The University of Tokyo), Edward Hirsch (Steklov Institute of Mathematics at St. Petersburg), Kaave Hosseini (UC San Diego), Valentine Kabanets (Simon Fraser University), Antonina Kolokolova (Memorial University of Newfoundland), Michal Koucky (Charles University), Sasha Kulikov (Steklov Institute of Mathematics at St. Petersburg), Meena Mahajan (Institute of Mathematical Sciences), Jenish Mehta (Caltech), Or Meir (University of Haifa), Dor Minzer (Tel Aviv University), Toni Pitassi (University of Toronto), Aaron Potechin (University of Chicago), Robert Robere (University of Toronto), Ben Rossman (University of Toronto), Rahul Santhanam (University of Oxford), Rocco Servedio (Columbia University), Sasha Sherstov (UCLA), Dmitry Sokolov (School of Computer Science and Communication at KTH University), Suguru Tamaki (Kyoto University), Li-Yang Tan (Stanford University), Roei Tell (Weizmann Institute of Science), Emanuele Viola (NEU), Avi Wigderson (Institute for Advanced Study), Ryan Williams (MIT)