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
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 4 January 2022
13:00
30 Minutes
Virtual talk
Virtual talk
Saarbrücken
Abstract
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.
Contact
Virtual Meeting Details
Zoom
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
If you wish to attend the talk, please contact Roohani Sharma rsharma@mpi-inf.mpg.de to obtain the password of the zoom talk.
Karl Bringmann, 01/04/2022 00:44
Roohani Sharma, 01/03/2022 20:17 -- Created document.
Roohani Sharma, 01/03/2022 20:17 -- Created document.