Workshops

Fall 2018

Lower Bounds in Computational Complexity Boot Camp

Aug 20, 2018 to Aug 24, 2018

Return to event »

Click on the titles of individual talks for abstract, slides and archived video.

Monday, August 20th, 2018
9:00 am–9:20 am		Coffee and Check-In
9:20 am–9:30 am		Opening Remarks
9:30 am–10:30 am		Circuit Lower Bounds from Algorithm Design: An Overview I Ryan Williams, MIT
10:30 am–11:00 am		Break
11:00 am–12:00 pm		Circuit Lower Bounds from Algorithm Design: An Overview II Ryan Williams, MIT
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Restriction-based Methods I Ben Rossman, University of Toronto
3:00 pm–3:30 pm		Break
3:30 pm–4:30 pm		Restriction-based Methods II Ben Rossman, University of Toronto
4:30 pm–6:00 pm		Welcome Reception

Tuesday, August 21st, 2018
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Lower Bounds Techniques in Proof Complexity I Pavel Hrubes, Academy of Sciences of the Czech Republic
10:30 am–11:00 am		Break
11:00 am–12:00 pm		Lower Bounds Techniques in Proof Complexity II Pavel Hrubes, Academy of Sciences of the Czech Republic
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Derandomization from Circuit Lower Bounds I Russell Impagliazzo, UC San Diego
3:00 pm–3:30 pm		Break
3:30 pm–4:30 pm		Derandomization from Circuit Lower Bounds II Russell Impagliazzo, UC San Diego

Wednesday, August 22nd, 2018
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 pm		Geometric Complexity Theory: Complexity Lower Bounds Using Algebraic Geometry and Representation Theory I Christian Ikenmeyer, Max Planck Institute for Informatics
10:30 am–11:00 am		Break
11:00 am–12:00 pm		Geometric Complexity Theory: Complexity Lower Bounds Using Algebraic Geometry and Representation Theory II Christian Ikenmeyer, Max Planck Institute for Informatics
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Lower Bounds in Arithmetic Circuit Complexity I Srikanth Srinivasan, Indian Institute of Technology Bombay
3:00 pm–3:30 pm		Break
3:30 pm–4:30 pm		Lower Bounds in Arithmetic Circuit Complexity II Srikanth Srinivasan, Indian Institute of Technology Bombay

Thursday, August 23rd, 2018
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 pm		Communication Complexity I Anup Rao, University of Washington
10:30 am–11:00 am		Break
11:00 am–12:00 pm		Communication Complexity II Anup Rao, University of Washington
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Lower Bounds for Dynamic Data Structures I Kasper Green Larsen, Aarhus University
3:00 pm–3:30 pm		Break
3:30 pm–4:30 pm		Lower Bounds for Dynamic Data Structures II Kasper Green Larsen, Aarhus University

Friday, August 24th, 2018
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Time-Space Lower Bounds for Learning I Avishay Tal, Stanford University
10:30 am–11:00 am		Break
11:00 am–12:00 pm		Time-Space Lower Bounds for Learning II Avishay Tal, Stanford University
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Impossibility Results for Distributed Computing I Faith Ellen, University of Toronto
3:00 pm–3:30 pm		Break
3:30 pm–4:30 pm		Impossibility Results for Distributed Computing II Faith Ellen, University of Toronto