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.

R. Shapiro Organizer's Page

Charles Weibel Organizer's Page

Brooke Logan

Wujun Zhang Organizer's webpage

Xiaojun Huang, Jian Song, Sagun Chanillo

Pranjal Awasthi, Shubhangi Saraf Organizer's Page

Jeffry Kahn, Bhargav Narayanan, Abigail Raz Organizer's webpage

Bryan Ek, Doron Zeilberger home page

Paul Feehan, Manousos Maridakis, Natasa Sesum seminar webpage

Borisov, Diaconescu, Tarasca, Woodward

Alejandro Ginory Organizer's Page

Louis Gaudet, Yael Davidov Organizer's webpage

Erik De Amorim Organizer's Page

Corrine Yap Organizer's webpage

Edna Jones Organizer's webpage

Yanyan Li, Zheng-Chao Han, Jian Song, Natasa Sesum

Lisa Carbone, Yi-Zhi Huang, James Lepowsky, Siddhartha Sahi Organizer's page

Grigor Sargsyan seminar website

Kasper Larsen, Daniel Ocone and Kim Weston Organizer's page

Joel Lebowitz, Michael Kiessling

Yanyan Li, Haim Brezis

Matthew C Welsh

Stephen D. Miller, John C. Miller, Alex V. Kontorovich, Claire Burrin seminar website

Stephen D. Miller

Organizers: Yanyan Li, Z.C. Han, Jian Song, Natasa Sesum

Matthew Charnley Organizer's Page

Hongbin Sun Organizer's page

Organizer: Vladimir Retakh Organizer's webpage

- Show events from all categories

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

*Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.*

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 |