Wednesday, December 10, 2008

Succincter

'Tis the season to be doing succinct data structures.


[P] My FOCS'08 paper demonstrated how to use recursion to achieve better redundancy. For many fundamental problems, it achieved a redundancy of n / (lg n / t)t bits with query time O(t). The toy problem that people remember from my paper is storing trits: store A[1..n], where A[i] in {1,2,3}, using close to n log23 bits and fast access to A[i].


[Golynski] In SODA'09, Alexander Golynski (PhD from Waterloo, currently at Google NY) showed a remarkable lower bound for succinct data structures. Suppose you want to represent a permutation π such that you can access π(x) and π-1(x) in time t. Then, your data structure needs redundancy Ω(n lg n / t2) bits. In particular, for constant access time, your data structure needs a constant factor more space than the minimum!

This is essentially the first "meaningful" lower bound for succinct data structures. [Gal-Miltersen] did prove a previous lower bound, but for a much harder problem: polynomial evaluation. (For this problem, we believe sublinear query time requires superpolynomial space, so never mind succinct data structures.)

Notice that Golynski's lower bound is much higher than my upper bound for storing trits and other problems. His bound is in fact tight for storing a permutation.


[Viola] Emanuele Viola looks at the trits problem in the bit-probe model and shows that, with bit probe complexity t, the redundancy needs to be at least n / 2O(t). My result implies a redundancy of n / 2O(sqrt{t}) if t is the bit-probe complexity. 

As I always want to point out, the true model is the word RAM, but the bit-probe model is sometimes interesting as a mathematical curiosity.


[Mitzenmacher-Wiener] Michael has a student working on an implementation of the results in my paper. You could've guessed it from here, I suppose.


[P.-Thorup] In recent ongoing work, we gave a very strong result for the trits problem: we can achieve a redundancy of exactly 2 bits, with O(1) query time. This completely kills the problem.

In the bit-probe model, it immediately implies an upper bound matching [Viola].

It is not yet clear whether such strong upper bounds can be extended beyond the trits problem (e.g., for dictionaries and arithmetic coding). But we have some ideas and we are working hard on it (i.e. drinking and hiking).


4 comments:

Wei Yu said...

Yesterday Avinatan talked about an interesting idea of using extractor as decoder to improve implicit data structure upper bounds.

Anonymous said...

"NP vs P" has been finally resolved by no less than Rafee Kamouna.

“Bi-Polarism Theory” is the solution to all our worries; does it come with a prescription drug ?

Anonymous said...

Dear Anonymous,

This is the first time I read it "NP vs. P",

Is this a new problem different Cook's P vs. NP. I presume not.

It is not finaly resolved, Sir. The (sad) result is that ZFC is (irreparablly) inconsistet.

Fuzzy logic programs form infinite counter-examples to the NP-completeness property.

The extensive peer-review process that is going on is clear on Prof Luca Trevisan blog.

I haven't issued a "Call for Opponents" yet, you join me there as the first one after the de facto opponent: Grand Prof Petr Hajek.

Best,

Rafee Kamouna.

Anonymous said...

Dear Anonymous,

I apologize. I thought you were mocking. Maybe not.

Happy New Year!

Best,

Rafee Kamouna.