« search calendars

« DIMACS Workshop on Lower Bounds and Frontiers in Data Structures

DIMACS Workshop on Lower Bounds and Frontiers in Data Structures

August 08, 2022 - August 11, 2022



Rutgers University

CoRE Building

96 Frelinghuysen Road

Piscataway, NJ 08854

Click here for map.


Toniann Pitassi, Columbia University

Mike Saks, Rutgers University

Omri Weinstein, Columbia University

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]


Monday, August 8, 2022

9:30 AM - 12:30 PM

Tutorial: Techniques for Static and Dynamic Cell-Probe Lower Bounds

Huacheng Yu, Princeton University

12:30 PM - 2:30 PM


2:30 PM - 3:30 PM

Memory Bounds for the Experts Problem

David P. Woodruff, Carnegie Mellon University

3:30 PM - 4:30 PM

Online List Labeling and History-Independence

Nicole Wein, DIMACS

4:30 PM - 5:30 PM

Lower Bounds for Semi-adaptive Data Structures via Corruption

Pavel Dvorak, Tata Institute of Fundamental Research


Tuesday, August 9, 2022

9:00 AM - 12:00 PM

Tutorial: Fine-Grained Lower Bounds in Data Structures

Amir Abboud, Weizmann Institute of Science

12:00 PM - 2:30 PM


2:30 PM - 3:30 PM

Tight Bounds for Monotone Minimal Perfect Hashing

Sepehr Assadi, Rutgers University

3:30 PM - 4:30 PM

Data Structure Lower Bounds in Cryptography

Kevin Yeo, Columbia University

4:30 PM - 5:30 PM

Dynamic Data Structures in Interior-Point Methods

Omri Weinstein, Columbia University

5:30 PM - 6:30 PM

Open Problem Session


Wednesday, August 10, 2022

9:00 AM - 12:00 PM

Tutorial: The Multiphase and OMV Conjectures, and Implications to Dynamic LBs

Kaspar Green Larsen, Aarhus University

12:00 PM - 2:30 PM


2:30 PM - 3:30 PM

On the Optimal Time/Space Tradeoff of Hashing Tables

John Kuszmaul, Yale University

3:30 PM - 4:30 PM

Dynamic Optimality in External Memory

Michael Bender, Stony Brook University

4:30 PM - 5:30 PM

Circuit Complexity of Kronecker Powers

Josh Alman, Columbia University


Thursday, August 11, 2022

9:00 AM - 12:00 PM

Arithmetic Data Structure Lower Bounds: Everything that we can prove (and nothing else)

Alexander Golovnev, Georgetown University

12:00 PM - 1:00 PM


1:00 PM - 2:00 PM

Open Group Discussion


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