Lower Bounds in Computational Complexity Boot Camp

Program

Lower Bounds in Computational Complexity

Location

Calvin Lab Auditorium

Date

Monday, Aug. 20 – Friday, Aug. 24, 2018

Back to calendar

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

9 – 9:20 a.m.

Coffee and Check-In

9:20 – 9:30 a.m.

Opening Remarks

9:30 – 10:30 a.m.

Circuit Lower Bounds from Algorithm Design: An Overview I

Ryan Williams (Massachusetts Institute of Technology)

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

Circuit Lower Bounds from Algorithm Design: An Overview II

Ryan Williams (Massachusetts Institute of Technology)

12 – 2 p.m.

Lunch

2 – 3 p.m.

Restriction-based Methods I

Benjamin Rossman (University of Toronto)

3 – 3:30 p.m.

Break

3:30 – 4:30 p.m.

Restriction-based Methods II

Benjamin Rossman (University of Toronto)

4:30 – 6 p.m.

Welcome Reception

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Lower Bounds Techniques in Proof Complexity I

Pavel Hrubes, Academy of Sciences of the Czech Republic

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

Lower Bounds Techniques in Proof Complexity II

Pavel Hrubes, Academy of Sciences of the Czech Republic

12 – 2 p.m.

Lunch

2 – 3 p.m.

Derandomization from Circuit Lower Bounds I

Russell Impagliazzo (UC San Diego)

3 – 3:30 p.m.

Break

3:30 – 4:30 p.m.

Derandomization from Circuit Lower Bounds II

Russell Impagliazzo (UC San Diego)

9 – 9:30 a.m.

Coffee and Check-In

9:30 a.m. – 10:30 p.m.

Geometric Complexity Theory: Complexity Lower Bounds Using Algebraic Geometry and Representation Theory I

Christian Ikenmeyer (University of Warwick)

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

Geometric Complexity Theory: Complexity Lower Bounds Using Algebraic Geometry and Representation Theory II

Christian Ikenmeyer (University of Warwick)

12 – 2 p.m.

Lunch

2 – 3 p.m.

Lower Bounds in Arithmetic Circuit Complexity I

Srikanth Srinivasan (Aarhus University)

3 – 3:30 p.m.

Break

3:30 – 4:30 p.m.

Lower Bounds in Arithmetic Circuit Complexity II

Srikanth Srinivasan (Aarhus University)

9 – 9:30 a.m.

Coffee and Check-In

9:30 a.m. – 10:30 p.m.

Communication Complexity I

Anup Rao (University of Washington)

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

Communication Complexity II

Anup Rao (University of Washington)

12 – 2 p.m.

Lunch

2 – 3 p.m.

Lower Bounds for Dynamic Data Structures I

Kasper Green Larsen (Aarhus University)

3 – 3:30 p.m.

Break

3:30 – 4:30 p.m.

Lower Bounds for Dynamic Data Structures II

Kasper Green Larsen (Aarhus University)

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Time-Space Lower Bounds for Learning I

Avishay Tal (UC Berkeley)

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

Time-Space Lower Bounds for Learning II

Avishay Tal (UC Berkeley)

12 – 2 p.m.

Lunch

2 – 3 p.m.

Impossibility Results for Distributed Computing I

Faith Ellen, University of Toronto

3 – 3:30 p.m.

Break

3:30 – 4:30 p.m.

Impossibility Results for Distributed Computing II

Faith Ellen, University of Toronto