Workshops
Fall 2018

Lower Bounds in Computational Complexity Boot Camp

Aug. 20 – Aug. 24, 2018

Add to Calendar

Program: 
Lower Bounds in Computational Complexity
View schedule & video »
View abstracts »

Organizers:

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

The Boot Camp is intended to acquaint program participants with the key themes of the program.

Enquiries may be sent to the organizerscomplexity2018 [at] lists [dot] simons [dot] berkeley [dot] edu ( at this address).

Registration is now CLOSED.

Talks

Circuit Lower Bounds from Algorithm Design: An Overview I
Speaker: Ryan Williams, MIT
Circuit Lower Bounds from Algorithm Design: An Overview II
Speaker: Ryan Williams, MIT
Restriction-based Methods I
Speaker: Ben Rossman, University of Toronto
Restriction-based Methods II
Speaker: Ben Rossman, University of Toronto
Lower Bounds Techniques in Proof Complexity I
Speaker: Pavel Hrubes, Academy of Sciences of the Czech Republic
Lower Bounds Techniques in Proof Complexity II
Speaker: Pavel Hrubes, Academy of Sciences of the Czech Republic
Derandomization from Circuit Lower Bounds I
Speaker: Russell Impagliazzo, UC San Diego
Derandomization from Circuit Lower Bounds II
Speaker: Russell Impagliazzo, UC San Diego
Geometric Complexity Theory: Complexity Lower Bounds Using Algebraic Geometry and Representation Theory I
Speaker: Christian Ikenmeyer, Max Planck Institute for Informatics
Geometric Complexity Theory: Complexity Lower Bounds Using Algebraic Geometry and Representation Theory II
Speaker: Christian Ikenmeyer, Max Planck Institute for Informatics
Lower Bounds in Arithmetic Circuit Complexity I
Speaker: Srikanth Srinivasan, Indian Institute of Technology Bombay
Lower Bounds in Arithmetic Circuit Complexity II
Speaker: Srikanth Srinivasan, Indian Institute of Technology Bombay
Communication Complexity I
Speaker: Anup Rao, University of Washington
Communication Complexity II
Speaker: Anup Rao, University of Washington
Lower Bounds for Dynamic Data Structures I
Speaker: Kasper Green Larsen, Aarhus University
Lower Bounds for Dynamic Data Structures II
Speaker: Kasper Green Larsen, Aarhus University
Time-Space Lower Bounds for Learning I
Speaker: Avishay Tal, Stanford University
Time-Space Lower Bounds for Learning II
Speaker: Avishay Tal, Stanford University
Impossibility Results for Distributed Computing I
Speaker: Faith Ellen, University of Toronto
Impossibility Results for Distributed Computing II
Speaker: Faith Ellen, University of Toronto