Talk at Berkeley

A long long time ago, when we took our first computers course, we learned that computers represent things in bits, not in base 10, since bits are easier to store (say, charged vs uncharged capacitor). Well, bits may be easier for computers, but apparently not much easier...

We can represent an array A[1..n] of digits using ceiling(n log₂ 10) bits on a regular computer, such that reading or writing any A[i] value can be done in constant time.

Come hear the details at my talk tommorow (Wednesday, 12pm, Wozniak lounge, Soda Hall, Berkeley). The write-up is forthcoming, and will be posted here.

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 log₂3 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 / t²) 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 / 2^O(t). My result implies a redundancy of n / 2^O(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).

B.A.M. 2

The Berkeley Algorithmists' Meeting will continue on Tuesday at 3:30pm.

Scheduling. There have been enough calls to change the time that I will do a recount of the votes and probably change it starting next week. If you would like to come and have not sent me your time constraints, please send them ASAP to mip@alum-mit-edu

Lecture notes. There are definite plans to post lecture notes here, though scheduling constraints will delay this for another week or so.

New topic: Orthogonal Range Queries

I want to spend a couple of meeting talking about range queries, a hugely important topic (in my opinion) that we don't teach too much of. The theory that has developed around this topic is one of the deepest examples of a coherent theory in TCS (maybe close to PCPs, depending on your subjective perception of depth).

Some ideas we will discuss, in an order TBD:

• persistence
  
• predecessor search (especially van Emde Boas)
• buffer trees
• RMQ
• the 3D structure of Nekrich
• rank/select
• lower bounds

Changes in TCS

At the first BAM, I got an idea of how little complexity theory has changed in three decades: after I described Morgenstern's lower bound for arithmetic circuits with bounded constants, Christos noted that he gave a talk about the same paper in 1978, when he was a postdoc at Berkeley. We still have no clue how to prove a superlinear lower bound in the unrestricted model.

At the same meeting, I got to observe a change in the people that define our community, a change that fed right into my anxiety that "Theory of Computer Science" is becoming "Theory." After I defined and drew a butterfly graph, I asked how many people have seen this before; some 3 or 4 people raised their hands (which drops to a very small number once you subtract Christos and Dick Karp). But when I asked who knew that "Fourier characters are orthogonal," all but one had their hands up!

I, for one, grew up thinking supercomputers were cool, and knew all about routing messages, before I learned about those "linear systems" that people apparently wanted to solve on big machines. And, yes, I am suspicious of people who had a "theory is cool!" moment before 100 "CS is cool!" moments.

Berkeley Algorithmists' Meetings

I am starting a new reading group at Berkeley. (Actually, I prefer the term "discussion group," since I was never too passionate about reading papers anyway; instead, I very much enjoy cafe-style discussion of open problems.)

For lack of a better name, this series will go by BAM (Berkeley Algorithmists' Meetings). Regarding coverage, I did not promise anything more specific than:

Since nobody can decide whether I'm doing complexity or algorithms, I will aim to keep this discussion group at the same level of ambiguity.

Presentations will transcend the boundaries of any single paper, as we will try to get a more comprehensive view of each topic, without getting bogged down in technicalities. We will talk amply about open problems.

I am hoping that all presentations will be transcribed as posts on this blog. Thus, feel free to request topics that you want to read about. You will get slightly less weight than the physical audience, but your comments will be heard.

The pilot meeting is this Tuesday, at 3:30pm. If you are in the area and would like to attend, check back tomorrow for the room details.

The topic for the first meeting is convolution and the FFT:

• how to think combinatorially about the FFT
• an Ω(nlg n) lower bound for arithmetic circuits with bounded coefficients [Morgenstern, JACM'73]
• an Ω(nlglg n) lower bound for offline range counting [Chazelle, STOC'95]
• discussion of open problems

Three Days in San Francisco

I started the week with a Misfits concert, those 31-year-old punk classics that have influenced all-time favorites like Slayer and Metallica.

Historical note: If the following are familiar to you...

• "Die, die, die, my darling..."
• "Here in this place lies the genie of death"
• "I got something to say: I killed your baby today"

... chances are it is the Metallica inflections that are now ringing in your head. However, it is worth remembering that these are originally Misfits songs.

I continued with Alistair Sinclair's "Mixing times for the solid-on-solid model". As usual, I think this is great theory, but not theory of computer science. (Here, Mikkel tries to make a similar point, cutting even deeper to define theory of computer science.)

Personal note: Attending such talks is always very interesting to me. In a short previous life, I was a Physicist (I even won 1st and 2nd prizes in the Romanian Physics Olympiad in '96 - '97). This left me with great physics intuition, but not that much mathematical intuition on how to formalize "physics proofs" (at that age, my appreciation of Math was very limited). It is very rewarding to catch up on the mathematical intuition, whenever I get a chance.

Finally, I had a chance to listen to some great music from Nels Cline and his band. This led to the interesting exercise of trying to triangulate Cline's heavy, academic jazz relative to black jazz and the Béla Bartók classical music.

The U.S. is a big country, but there are not many places where you can hear the Misfits, Sinclair, and Cline in a span of three days.

STOC

I decided yesterday not to submit anything to STOC, so I spent my most relaxing deadline day yet. For one paper, I found a deadly bug, while for another I found an improvement (moving it back to the column of things I need to think more about).

The main lesson for me was that there are limits to everything, and that dealing with an endless stream of stuff (from my defense, to writing a thesis, to visa issues, to searching for an apartment, to IBM sign on stuff, to paperwork for buying a motorcycle...) can really kill research.

Now I look forward to a year without deadlines (I am on the FOCS program committee). I hope to spend the first month catching up with things, and the rest doing what I actually enjoy doing, i.e. thinking about my problems. If this plan fails, I might have to elope to Africa again for a few months :)

As for this blog, I will probably get back to writing interesting technical stuff soon. I expect the non-technical stuff to be kept to a minimum. (For one, we've got too much blogging in the community, and I'm bored. Plus, I've felt disappointed with the TCS community for quite a while, and there's not much I can say in between lying and insulting some folks.)