STOC Tutorial on Algorithms for Memory-Sensitive Computing

Memory effects -- be they cache misses or page misses -- can have a dominant impact on the running time of an algorithm. In the case of page misses, a disk seek can be more than six orders of magnitude slower than a CPU instruction. Thus, even small savings in the number of memory transfers can have a large impact on running time.

This disproportionate importance of the memory hierarchy, combined with the large and growing appetite for large data, make memory-sensitive algorithms an area with active technology transfer from algorithmics to the rest of computer science and to the commercial world. This workshop focuses on algorithmic approaches that have seen high impact outside of academic TCS. The tutorials themselves will highlight the importance of algorithmic advances in making the technology possible.

May 19th, 2011

Location NYU Courant Institute

Registration is free for STOC attendees.

---

1:30-2:30 The History of I/O Models

Erik Demaine, MIT

2:30-3:30 I/O and Geometry

Pankaj Agarwal, Duke and Scalgo, Inc
Lars Arge, Aarhus and Scalgo, Inc

3:30-4:00 Break

4:00-5:00 I/O and Strings

Paolo Ferragina, Pisa

5:00-6:00 I/O and Databases

Michael Bender, Stony Brook and Tokutek, Inc
Martin Farach-Colton, Rutgers and Tokutek, Inc