Workshops

Fall 2018

Interactive Complexity

Oct 15, 2018 to Oct 18, 2018

Return to event »

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

Monday, October 15th, 2018
9:00 am–9:20 am		Coffee and Check-In
9:20 am–9:30 am		Welcome Remarks
9:30 am–10:30 am		The Hardest Halfspace Alexander Sherstov (UCLA)
10:30 am–11:00 am		Break
11:00 am–11:30 am		Lower Bounds for Elimination via Weak Regularity Michal Koucky (Charles University)
11:30 am–12:00 pm		Round Elimination using Triangular Discrimination Amir Yehudayoff (Technion Israel Institute of Technology)
12:00 pm–2:00 pm		Lunch
2:00 pm–2:30 pm		Quantum Algorithms for Composed Functions With Shared Inputs Justin Thaler (Georgetown University)
2:30 pm–3:00 pm		Open Problems in Number-On-Forehead Communication Complexity Toni Pitassi (University of Toronto)
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		Bounded Independence Plus Noise, and the Communication Complexity of Decoding Emanuele Viola (Northeastern University)
4:00 pm–4:30 pm		Network Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All Sumegha Garg (Princeton University)
4:30 pm–6:00 pm		Open Problem Session

Tuesday, October 16th, 2018
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Advances in Linear Sketching over Finite Fields Grigory Yaroslavtsev (Indiana University, Bloomington)
10:30 am–11:00 am		Break
11:00 am–11:30 am		Strong Direct Sum for Randomized Query Complexity Joshua Brody (Swarthmore College)
11:30 am–12:00 pm		On a Composition Theorem for Randomized Query Complexity Troy Lee (Nanyang Technological University)
12:00 pm–2:00 pm		Lunch
2:00 pm–2:30 pm		Distributed Interactive Proofs Rotem Oshman (Tel Aviv University)
2:30 pm–3:00 pm		Yes, There is an Oblivious RAM Lower Bound! Kasper Green Larsen (Aarhaus University)
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		Time-Space Tradeoffs for the Memory Game Amit Chakrabarti (Dartmouth College)
4:00 pm–4:30 pm		Sparse Trace Reconstruction Andrew McGregor (University of Massachusetts, Amherst)
4:30 pm		Reception

Wednesday, October 17th, 2018
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Static Data Structure Lower Bounds Imply Rigidity Omri Weinstein (Columbia University)
10:30 am–11:00 am		Break
11:00 am–11:30 am		Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers Siva Natarajan Ramamoorthy (University of Washington)
11:30 am–12:00 pm		Simulation beats Richness: New Data-Structure Lower Bounds Arkadev Chattopadhyay (Tata Institute of Fundamental Research)
12:00 pm–2:00 pm		Lunch
2:00 pm–2:30 pm		Why Extension-Based Proofs Fail Faith Ellen (University of Toronto)
2:30 pm–3:00 pm		Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication Diptarka Chakraborty (Charles University)
		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, October 18th, 2018
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Sparse MDS Matrices: Proof of the GM-MDS Conjecture Shachar Lovett (UC San Diego)
10:30 am–11:00 am		Break
11:00 am–11:30 am		On the Deterministic Complexity of Counting Events in a Stream T.S. Jayram (IBM Almaden)
11:30 am–12:00 pm		Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation Huacheng Yu (Harvard University)
12:00 pm–2:00 pm		Lunch
2:00 pm–2:30 pm		The Sketching Complexity of Graph and Hypergraph Counting Michael Kapralov (École Polytechnique Fédérale de Lausanne)
2:30 pm–3:00 pm		Distributed Statistical Estimation of Matrix Products with Applications Qin Zhang (Indiana University, Bloomington)
3:00 pm–3:30 pm		Fully Understanding The Hashing Trick Lior Kamma (Aarhus University)