- Talk: Cell-Probe Lower Boun...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in May 2017
Talk: Cell-Probe Lower Bounds from Online Communication Complexity
Speaker:
Josh Alman
, CSAIL MIT
Date: Wednesday, May 24, 2017
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Public: Yes
Location: 32-G575
Event Type:
Room Description:
Host: Pritish Kamath and Akshay Degwekar, CSAIL MIT
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Speaker URL: None
Speaker Photo:
None
Reminders to:
seminars@csail.mit.edu, theory-seminars@csail.mit.edu
Reminder Subject:
TALK: Josh Alman:Cell-Probe Lower Bounds from Online Communication Complexity
Abstract: In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players Bob his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result it presents Bob with the next piece. This model has a closer and more natural correspondence to dynamic data structures than the classic communication models do and hence presents a new perspective on data structures.
We first present a lower bound for the online set intersection problem in the online communication model, demonstrating a general approach for proving online communication lower bounds. The online communication model prevents a batching trick that classic communication complexity allows, and yields a stronger lower bound. Then we apply the online communication model to data structure lower bounds by studying the Group Range Problem, a dynamic data structure problem. This problem admits an O(log n)-time worst-case data structure. Using online communication complexity, we prove a tight cell-probe lower bound: spending o(log n) (even amortized) time per operation results in at best an exp(-\delta^2 n) probability of correctly answering a (1/2 + \delta)-fraction of the n queries.
Joint work with Joshua Wang and Huacheng Yu.
Research Areas:
Impact Areas:
Created by Rebecca Yadegar at Wednesday, May 17, 2017 at 12:58 PM.