Kasper Green Larsen: Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

Speaker: Kasper Green Larsen, Asst. Professor, Dept. of Computer Science, Aarhus University

Date: Tuesday, November 28, 2017

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: Patil/Kiva G449

Event Type: Seminar

Room Description:

Host: Virginia Vassilevska Williams

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL:

Speaker Photo:

Reminders to: seminars@csail.mit.edu

Reminder Subject: TALK: Kasper Green Larsen: Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

Abstract: In this talk, we prove the first super-logarithmic lower bounds on the
cell probe complexity of dynamic boolean (a.k.a. decision) data structure
problems, a long-standing milestone in data structure lower bounds.
We introduce a new method for proving dynamic cell probe lower bounds
and use it to prove a ??(lg^(1.5)n)
lower bound on the operational time of a wide range of boolean data
structure problems, most notably, on the query time of dynamic range
counting over F2 ([Pat'07]). Proving an ?(lgn)
lower bound for this problem was explicitly posed as one of five
important open problems in the late Mihai Patrascu's obituary [Tho'13].
This result also implies the first ?(lgn)
lower bound for the classical 2D range counting problem, one of the
most fundamental data structure problems in computational geometry and
spatial databases. We derive similar lower bounds for boolean versions
of dynamic polynomial evaluation and 2D rectangle stabbing, and for the
(non-boolean) problems of range selection and range median.
Our technical centerpiece is a new way of ``weakly" simulating dynamic
data structures using efficient one-way
communication protocols with small advantage over random guessing. This
simulation involves a surprising excursion to low-degree (Chebychev)
polynomials which may be of independent interest, and offers an entirely
new algorithmic angle on the ``cell sampling" method of Panigrahy et
al. [PTW'10].
Joint work with: Omri Weinstein and Huacheng Yu

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) 2017.

Created by Deborah Goodwin at Thursday, November 02, 2017 at 10:05 AM.