# 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