Campus Event Calendar

Event Entry

What and Who

Tight Fine-Grained Bounds for Direct Access on Join Queries, or: Fine-Grained Complexity meets Databases

Karl Bringmann
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 4 January 2022
30 Minutes
Virtual talk
Virtual talk


We present work at the intersection of fine-grained complexity and database theory. As our main result, for each "join query" we determine the optimal preprocessing time that allows constant-time "direct access", assuming the Zero-k-Clique hypothesis. In the talk, all database concepts will be explained with graphs and hypergraphs.

Based on joint work with Nofar Carmeli and Stefan Mengel.


Roohani Sharma
+49 681 9325 1116

Virtual Meeting Details

passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk, please contact Roohani Sharma to obtain the password of the zoom talk.

Karl Bringmann, 01/04/2022 00:44
Roohani Sharma, 01/03/2022 20:17 -- Created document.