Home
View: Month |
Event list |
Past events list
CSEE
November 2009
November
30
End Date
SciGPU Seminar
Maxwell Dworkin 319
GPU-accelerated Correlation of Images from the International Space Station, Peter J. Lu, Postdoctoral Research Fellow, Department of Physics, Harvard University
December 2009
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
2
End Date
IIC Colloquium
Maxwell Dworkin G115
Harvard Catalyst Profiles: Network Analysis and Data Visualization, Griffin Weber
December
3
End Date
December
14
End Date