Interactive Complexity

Program

Lower Bounds in Computational Complexity

Location

Calvin Lab Auditorium

Date

Monday, Oct. 15 – Thursday, Oct. 18, 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.

Welcome Remarks

9:30 – 10:30 a.m.

The Hardest Halfspace

Alexander Sherstov (UCLA)

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

Lower Bounds for Elimination via Weak Regularity

Michal Koucky (Charles University)

11:30 a.m. – 12 p.m.

Round Elimination using Triangular Discrimination

Amir Yehudayoff (Technion Israel Institute of Technology)

12 – 2 p.m.

Lunch

2 – 2:30 p.m.

Quantum Algorithms for Composed Functions With Shared Inputs

Justin Thaler (Georgetown University)

2:30 – 3 p.m.

Open Problems in Number-On-Forehead Communication Complexity

Toni Pitassi (University of Toronto)

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

Bounded Independence Plus Noise, and the Communication Complexity of Decoding

Emanuele Viola (NEU)

4 – 4:30 p.m.

Network Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All

Sumegha Garg (Harvard University)

4:30 – 6 p.m.

Open Problem Session

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Advances in Linear Sketching over Finite Fields

Grigory Yaroslavtsev (Indiana University, Bloomington)

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

Strong Direct Sum for Randomized Query Complexity

Joshua Brody (Swarthmore College)

11:30 a.m. – 12 p.m.

On a Composition Theorem for Randomized Query Complexity

Troy Lee (Nanyang Technological University)

12 – 2 p.m.

Lunch

2 – 2:30 p.m.

Distributed Interactive Proofs

Rotem Oshman (Tel Aviv University)

2:30 – 3 p.m.

Yes, There is an Oblivious RAM Lower Bound!

Kasper Green Larsen (Aarhus University)

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

Time-Space Tradeoffs for the Memory Game

Amit Chakrabarti (Dartmouth College)

4 – 4:30 p.m.

Sparse Trace Reconstruction

Andrew McGregor (University of Massachusetts Amherst)

4:30 p.m. PT

Reception

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Static Data Structure Lower Bounds Imply Rigidity

Omri Weinstein (Columbia University)

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers

Siva Natarajan Ramamoorthy (University of Washington)

11:30 a.m. – 12 p.m.

Simulation beats Richness: New Data-Structure Lower Bounds

Arkadev Chattopadhyay (Tata Institute of Fundamental Research)

12 – 2 p.m.

Lunch

2 – 2:30 p.m.

Why Extension-Based Proofs Fail

Faith Ellen (University of Toronto)

2:30 – 3 p.m.

Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication

Diptarka Chakraborty (Charles University)

4 p.m. PT

All workshop participants are cordially invited to the UC Berkeley Department of Electrical Engineering and Computer Sciences (EECS)'s ACM A.M. Turing Laureate Colloquium featuring a talk by 1995 laureate Manuel Blum.

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Sparse MDS Matrices: Proof of the GM-MDS Conjecture

Shachar Lovett (UC San Diego)

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

On the Deterministic Complexity of Counting Events in a Stream

T.S. Jayram Jayram (IBM Almaden Research)

11:30 a.m. – 12 p.m.

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

Huacheng Yu (Harvard University)

12 – 2 p.m.

Lunch

2 – 2:30 p.m.

The Sketching Complexity of Graph and Hypergraph Counting

Michael Kapralov (Ecole Polytechnique Fédérale de Lausanne)

2:30 – 3 p.m.

Distributed Statistical Estimation of Matrix Products with Applications

Qin Zhang (Indiana University, Bloomington)

3 – 3:30 p.m.

Fully Understanding The Hashing Trick

Lior Kamma (Aarhus University)