Home
View: Month |
Event list |
Past events list
All SEAS Calendars
November 2009
November
26
End Date
Thanksgiving
Thanksgiving Holiday
November
26
End Date
Thanksgiving Recess
Thanksgiving recess for students
December 2009
December
2
End Date
December
2
End Date
Lower bounds for succinct data structures, Emanuele Viola, Northeastern University
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.
We also prove lower bounds for other fundamental data structure problems, including: storing a set so that membership queries can be answered efficiently, storing a bit-string so that prefix sums can be computed efficiently, and storing a string of brackets so that matching brackets can be found efficiently.
Part of this work is joint with Mihai Patrascu
December
3
End Date
December
3
End Date
December
4
End Date
Fall Reading Period
Fall Reading Period is from December 4 - December 11
December
8
End Date
CS 50 Fair
Northwest Science Labs at 52 Oxford St
WHAT: The CS 50 Fair
WHEN: Tuesday December 8, 1:00pm – 4:30pm (may start at 1pm instead)
WHERE: Northwest Science Labs at 52 Oxford St
December
10
End Date
December
12
End Date
Fall Term Final Examinations Begin
Fall Term Final Examinations are from December 12 - December 21
December
14
End Date
December
16
End Date
December
22
End Date
Winter Recess
Winter Recess at Harvard (University is closed from Dec 22-Jan 3)
December
22
End Date
Winter Recess
Winter Recess is from December 22 - January 3
January 2010
January
18
End Date
First Day Spring Classes
First Day of Spring Classes and Registration Begins
January
18
End Date
Martin Luther King Day
Martin Luther King Day Holiday
January
29
End Date
Study Card Day
Study cards are due
February 2010
February
15
End Date
President's Day
President's Day Holiday
March 2010
March
13
End Date
Spring Recess
Spring Recess is from March 13 - March 21
April 2010
April
28
End Date
April
29
End Date
Spring Reading Period
Spring Reading Period is from April 29 - May 6
May 2010
May
7
End Date
Sping Term Final Examinations
Spring Term Final Examinations take place from May 7 - May 15
May
27
End Date
May
31
End Date
Memorial Day
Memorial Day Holiday