Tuesday, January 20, 2009

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 log2 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.

5 comments:

ilyaraz said...

Isn't it generalization of your trits paper?

MiP said...

It's an improvement of my FOCS paper... There, the redundancy was n / polylog(n), while now it is essentially zero.

ilyaraz said...

seems intriguing

Anonymous said...

FYI:

http://eccc.hpi-web.de/eccc-reports/2009/TR09-005/index.html

Pat Morin said...

Mihai, have you written this down yet? Did you make slides for your presentation?

I'm gathering material for my graduate data structures class and am curious to see if this is something I can include.