Workshop Details

The PDF documents linked on this page, are no longer maintained and may not meet accessibility standards. To request an accessible version of any content, please contact us.

Data structures (DS) are the backbone of algorithm design and information retrieval. They underlie the performance of most industry-scale applications, from internet routing and road navigation, to Cloud storage, similarity search, compression and machine learning. As such, understanding what data structures can and cannot compute efficiently is a fundamental question in both theory and practice.

Despite roughly 70 years of successful research in data structures and algorithms, there are still exponential gaps between best known upper and lower bounds for many basic data structure problems. These include dynamic reachability and flow queries in graphs, pattern-matching, set similarity search, and online matrix multiplication, among many others. In recent years, communication complexity and information theory have emerged as powerful mathematical tools for analyzing time-space tradeoffs and proving unconditional lower bounds on static and dynamic data structures, and (perhaps more surprisingly), in recent developments in fine-grained complexity, i.e., proving conditional lower bounds for hardness of approximation of offline and online problems.

The purpose of the workshop is to bring together complexity theorists and fine-grained algorithms experts, to promote discussion and collaboration on some of the major open problems in the field of data structures and dynamic algorithms (e.g., the "Multiphase" conjecture and the Online Matrix-Vector (OMV) conjecture, cell-probe lower bounds, Dynamic Optimality etc.). The workshop will also explore Connections between data structures and complexity theory, in particular, to locally-decodable codes (LDCs), circuit complexity, matrix rigidity and algebraic geometry. 

Each day will begin with a tutorial one one of the central topics of the workshop. Apart from tutorials, the workshop will encourage talks presentations that spark discussion and collaborations on open problems and technical frontiers in the field, as well as connection and applications of DS in other fields of TCS. The schedule will leave substantial room for offline collaboration and small group meetings.

View tentative schedule: [PDF].

View video playlist: [Youtube]