[Colloq] Talk, Friday, May 8 - Emanuele Viola

[Rachel Kalweit]

The College of Computer and Information Science presents a talk by:

Speaker: Emanuele Viola

Date: Friday, May 8
Time: 1:00pm 
Location: 366 West Village H

TITLE: Bits vs. Trits

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.