Organizer(s):

Toniann Pitassi, Columbia University

Mike Saks, Rutgers University

Omri Weinstein, Columbia University

Description

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]

Program

Monday, August 8, 2022

Tuesday, August 9, 2022

Wednesday, August 10, 2022

Thursday, August 11, 2022

Call For Participation

This event is by invitation. If you would like to receive an invitation, please send email to either the DIMACS Workshop Coordinator or one of the organizers expressing your desire to attend. Such requests should be made at least five days before the start of the event.

COVID-19 Protocols: As required by Rutgers University, attendees must show proof of vaccination to attend. Additionally, DIMACS requests that masks be worn in the lecture room and other crowded indoor spaces. (Click here for more detailed information on COVID-19 policies.)

Code of Conduct

Presented in association with the Special Focus on Lower Bounds in Computational Complexity.