Dept Banner
Dept Banner

Calendar - Weekly View

Download as iCal file

DIMACS Theory of Computing Seminar

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

Omri Weinstein, Columbia University

Location:  NOTE: DIFFERENT LOCATION -- Core 431
Date & time: Wednesday, 08 November 2017 at 11:00AM - 12:00PM

Abstract:  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 technique and use it to prove a (log^{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 F_2* ([Patrascu07]). Proving an omega(log n) lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Patrascu's obituary [Thorup13]. This also implies the first omega(log n) 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. [PTW10].

 Joint work with Kasper Green Larsen and Huacheng Yu.


Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530