Abstract: 

Efficient data structures are the core of many algorithms and the design of data structures is a classical topic covered in most introductory text books on algorithms. Most algorithmic text books assume that a good approximation of a computer is the RAM (Random Access Machine) model of computation, where it assumed that each memory access and register computation takes one time unit. The high popularity of the RAM model in algorithm and data structure design is due to the model’s simplicity while traditionally allowing for a good estimate of running time on actual computers. Unfortunately, modern computer architectures deviate from the classical RAM model in many aspects, invalidating the basic assumption of  unit cost for each primitive instruction. This fact has sparked a lot of algorithmic research trying to model the essential bottlenecks in modern computer hardware and to understand the inherent trade-offs between the different limitations.  This talk will provide an overview of various directions in data structures ­­­­research for various models of computation.