Events — Colloquia & Seminars
Bits vs. Trits
Speaker: Emanuele Viola, Northeastern University
Date: Friday, May 8, 2009
Talk: 1:00 PM, 366 WVH
Abstract
It's the end of the semester, and you need to store on a computer your N students' grades from the 3-element universe {pass, fail, borderline}. Via so-called arithmetic coding you can store them using the minimum number of bits, N(log_2 3) + O(1), but then to retrieve a grade you need to read all the bits. Or you can use two distinct bits per grade, but then you waste a linear amount of space.
A breakthrough by Patrascu (FOCS 2008), later refined with Thorup, shows how to store the grades using the minimum number of bits so that each grade can be retrieved by reading just O(log N) bits.
We prove a matching lower bound: To retrieve the grades by reading b bits, space N(log_2 3) + N/2^b is necessary.
Brief Biography
none provided