Skip to main content
Search
Utility navigation
Calendar
Contact
Login
MAKE A GIFT
Main navigation
Home
Programs & Events
Research Programs
Workshops & Symposia
Public Lectures
Research Pods
Internal Program Activities
Algorithms, Society, and the Law
People
Scientific Leadership
Staff
Current Long-Term Visitors
Research Fellows
Postdoctoral Researchers
Scientific Advisory Board
Governance Board
Industry Advisory Council
Affiliated Faculty
Science Communicators in Residence
Law and Society Fellows
Participate
Apply to Participate
Plan Your Visit
Location & Directions
Postdoctoral Research Fellowships
Law and Society Fellowships
Science Communicator in Residence Program
Circles
Breakthroughs Workshops and Goldwasser Exploratory Workshops
Support
Annual Fund
Funders
Industrial Partnerships
News & Videos
News
Videos
About
Image
Interactive Complexity
Program
Lower Bounds in Computational Complexity
Location
Calvin Lab Auditorium
Date
Monday, Oct. 15
–
Thursday, Oct. 18, 2018
Back to calendar
Breadcrumb
Home
Workshop & Symposia
Schedule
Secondary tabs
The Workshop
Schedule
Videos
Click on the titles of individual talks for abstract, slides and archived video.
Monday, Oct. 15, 2018
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 (Northeastern University)
4
–
4:30 p.m.
Network Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All
Sumegha Garg (Princeton University)
4:30
–
6 p.m.
Open Problem Session
Tuesday, Oct. 16, 2018
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
Wednesday, Oct. 17, 2018
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.
Thursday, Oct. 18, 2018
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 (IBM Almaden)
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)
Share this page
Copy URL of this page
link to homepage
Close
Main navigation
Home
Programs & Events
Research Programs
Workshops & Symposia
Public Lectures
Research Pods
Internal Program Activities
Algorithms, Society, and the Law
People
Scientific Leadership
Staff
Current Long-Term Visitors
Research Fellows
Postdoctoral Researchers
Scientific Advisory Board
Governance Board
Industry Advisory Council
Affiliated Faculty
Science Communicators in Residence
Law and Society Fellows
Participate
Apply to Participate
Plan Your Visit
Location & Directions
Postdoctoral Research Fellowships
Law and Society Fellowships
Science Communicator in Residence Program
Circles
Breakthroughs Workshops and Goldwasser Exploratory Workshops
Support
Annual Fund
Funders
Industrial Partnerships
News & Videos
News
Videos
About
Utility navigation
Calendar
Contact
Login
MAKE A GIFT
link to homepage
Close
Search