FOCS 2012 Workshop on Data Structures
(in memory of Mihai Pătraşcu)



Date: Saturday, October 20, 2012.
Location: Hyatt Regency, New Brunswick, NJ.
Synopsis:
The field of data structures has seen many exciting developments in the recent years. The workshop will present tutorial-style talks covering those developments, including both upper and lower bounds. The talks will also cover the outstanding open problems in the area.

The workshop is dedicated to the memory of Mihai Pătraşcu, who has made fundamental contributions to the field. Mihai passed away in June 2012.
Schedule:
Time Speaker Title
9:00-9:45 Timothy Chan Mihai's Work in Computational Geometry
9:45-10:30 Liam Roditty Distance Oracles
10:30-11:00 Coffee Break (provided)
11:00-11:45 John Iacono Upper Bounds for Dictionaries
11:45-12:30 Rasmus Pagh Approximate Set Representations
12:30-2:30 Lunch break (on your own)
2:30-2:50 Erik Demaine My Student and Friend
2:50-3:25 Mikkel Thorup On Searching Predecessors and the Limitations of Linear Space
3:25-4:00 Alex Andoni Lower Bounds for High-Dimensional Nearest Neighbor Problems
4:00-4:30 Coffee Break (provided)
4:30-5:15 Kasper Green Larsen Lower Bounds for Dynamic Data Structures
5:15-6:00 Tonian Pitassi Lopsided Communication Complexity and
Polynomial Lower Bounds for Dynamic Problems
See also: Mikkel Thorup, "The Work of Mihai Pătraşcu", Sunday, 8pm.

Organizers: Alex Andoni, Erik Demaine, Piotr Indyk, Mikkel Thorup.