Title: Lower Bounds for Succinct Data Structures
Speaker: Mihai Patrascu, AT&T Labs
Date: Wednesday, September 16, 2009 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Suppose you want to store an array A[1..n] of bits by a data structure using as close to n bits as possible, and answer queries of the form sum(k) = A[1]+...+A[k]. This is a staple problem in the field of "succinct data structures."
I will prove a lower bound showing that, if we answer sum(k) queries by probing t cells of w bits, then the space of the data structure must be at least n + n/w^{O(t)} bits. This redundancy/time trade-off is essentially optimal, matching my [FOCS'08] upper bound. I will conclude with perspectives on the field of succinct data structures.