Succinter

Abstract

How can we represent an arrray A[1..n] with elements from {1,2,3}, supporting indexing operations?

* using arithmetic coding, we can achieve ceiling(n*log_2 3) bits (a redundancy of <1 bit), but one needs to decode the entire array to access a single element.

* using 4n bits (a redundancy of O(n) bits), one can index in constant time. In fact, by block-coding and table look-up, we can achieve constant running time with redundancy O(n/lg n). Standard techniques from succinct data structures and compression can trade off redundancy and access time linearly: allowing time t for indexing, one can achieve a redundancy of O(n/(t lgn)). We present a way to recurse for better redundancy, achieving redundancy O(n / lg^t n) for access time t.

This translates into improved bounds for a wide class of succinct data structures that have been studied in the literature.

BIO: Mihai Patrascu is a PhD student (expected graduation Aug'08) at MIT, working in theoretical computer science. His work is primarily focused in advanced data structures, especially lower bounds. Mihai obtained his Bachelor's in Mathematics in 2006, also from MIT. He received CRA's Outstanding Undergraduate Research Award in 2005. In his precollege years, spent in Romania, Mihai obtained a number of medals in international computer olympiad